Round #2

题源:来自hzwer整理的题

2014-5-10 NOIP模拟赛

by coolyangzc

Problem 1 机器人(robot.cpp/c/pas)

【题目描述】

早苗入手了最新的Gundam模型。最新款自然有着与以往不同的功能,那就是它能够自动行走,厉害吧。

早苗的新模型可以按照输入的命令进行移动,命令包括‘E’、‘S’、‘W’、‘N’四种,分别对应东南西北。执行某个命令时,它会向对应方向移动一个单位。作为新型机器人,它可以执行命令串。对于输入的命令串,每一秒它会按命令行动一次。执行完命令串的最后一个命令后,会自动从头开始循环。在0时刻时机器人位于(0,0)。求T秒后机器人所在位置坐标。

【输入格式】

第1行:一个字符串,表示早苗输入的命令串,保证至少有1个命令

第2行:一个正整数T

【输出格式】

2个整数,表示T秒时,机器人的坐标。

【样例输入】

NSWWNSNEEWN

12

【样例输出】

-1 3

【数据范围】

对于60%的数据 T<=500,000 且命令串长度<=5,000

对于100%的数据 T<=2,000,000,000 且命令串长度<=5,000

【注意】

向东移动,坐标改变改变为(X+1,Y);

向南移动,坐标改变改变为(X,Y-1);

向西移动,坐标改变改变为(X-1,Y);

向北移动,坐标改变改变为(X,Y+1);

简单模拟题,按照题意从原点(0,0)开始跑一遍命令串cmd,得出cmd[i]时相对于原点的位置,先T-=1再令x=T/|cmd|,y=T%|cmd|,得出机器人沿着命令串cmd跑了x轮,当前停留在命令串y的位置,即可算出答案x*cmd[|cmd|-1]+cmd[y];

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<utility>
#include<numeric>
#include<iterator>
#include<algorithm>
#include<functional>
#include<ctime>
#include<cassert>
using std::cin;
using std::cout;
using std::endl;
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
#define FOR(i,init,len) for(int i=(init);i<(len);++i)
#define For(i,init,len) for(int i=(init);i<=(len);++i)
#define fi first
#define se second
#define pb push_back
#define is insert
namespace IO {
inline char getchar() {
static const int BUFSIZE=;
static char buf[BUFSIZE],*begin,*end;
if(begin==end) {
begin=buf;
end=buf+fread(buf,,BUFSIZE,stdin);
if(begin==end) return -;
}
return *begin++;
}
}
inline void read(int &in) {
int c,symbol=;
while(isspace(c=IO::getchar()));
if(c=='-') { in=;symbol=-; }
else in=c-'';
while(isdigit(c=IO::getchar())) { in*=;in+=c-''; }
in*=symbol;
}
inline int read() { static int x;read(x);return x; }
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
#define PA(name,init,len) cout<<#name"["<<(len-init)<<"]=";FOR(_,init,len) cout<<name[_]<<" \n"[_==(len-1)];
#define Pa(name,init,len) cout<<#name"["<<(len-init+1)<<"]=";For(_,init,len) cout<<name[_]<<" \n"[_==(len)];
#define PV(name) cout<<#name"="<<name<<'\n'; const int dx[]={,,-,};
const int dy[]={,,,-};
int c[];
std::vector<P> v;
std::string s;
int T; int main() {
#ifdef MengLan
int Beginning=clock();
//freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif // MengLan cin>>s>>T;
P now(,);
c['E']=;c['N']=;c['W']=;c['S']=;
for(auto ch:s){
int dir=c[ch];
now=P(now.fi+dx[dir],now.se+dy[dir]);
v.pb(now);
}
--T;
int x=T/s.size(),y=T%s.size();
//PV(x)PV(y)
printf("%d %d\n",v.back().fi*x+v[y].fi,v.back().se*x+v[y].se); #ifdef MengLan
printf("Time: %d\n",clock()-Beginning);
system("pause");
#endif // MengLan
return ;
}

Problem 2 数列(seq.cpp/c/pas)

【题目描述】

a[1]=a[2]=a[3]=1

a[x]=a[x-3]+a[x-1]  (x>3)

求a数列的第n项对1000000007(10^9+7)取余的值。

【输入格式】

第一行一个整数T,表示询问个数。

以下T行,每行一个正整数n。

【输出格式】

每行输出一个非负整数表示答案。

【样例输入】

3

6

8

10

【样例输出】

4

9

19

【数据范围】

对于30%的数据 n<=100;

对于60%的数据 n<=2*10^7;

对于100%的数据 T<=100,n<=2*10^9;

众所周知,求fib(斐波那契数列)第n项f[n]%mod可以通过矩阵快速幂求得,而且本题和fib一样都属于线性递推,那么只需要构造一个矩阵A,使得

f(x)   a1 b1 c1   f(x-1)
f(x-1) = a2 b2 c2 * f(x-2)
f(x-2)   a3 b3 c3   f(x-3)

则可以通过矩阵左乘一次A,从f(x)推出下一项f(x+1),已知前三项均为1,则可以通过左乘A^(n-3)推出f(n);

那么依据矩阵乘法:

f(x)=a1*f(x-1)+b1*f(x-2)+c1*f(x-3)

f(x-1)=a2*f(x-1)+b2*f(x-2)+c2*f(x-3)

f(x-2)=a3*f(x-1)+b3*f(x-2)+c3*f(x-3)

由于本题f(x)=f(x-1)+f(x-3)

那么显然系数为:

a1=1,b1=0,c1=1;

a2=1,b2=0,c2=0;

a3=0,b3=1,c3=0;

那么直接通过矩阵快速幂算得A^(n-3)即可解决;

由于本人比较懒,代码直接使用3*3矩阵进行运算;

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<utility>
#include<numeric>
#include<iterator>
#include<algorithm>
#include<functional>
#include<ctime>
#include<cassert>
using std::cin;
using std::cout;
using std::endl;
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
#define FOR(i,init,len) for(int i=(init);i<(len);++i)
#define For(i,init,len) for(int i=(init);i<=(len);++i)
#define fi first
#define se second
#define pb push_back
#define is insert
namespace IO {
inline char getchar() {
static const int BUFSIZE=;
static char buf[BUFSIZE],*begin,*end;
if(begin==end) {
begin=buf;
end=buf+fread(buf,,BUFSIZE,stdin);
if(begin==end) return -;
}
return *begin++;
}
}
inline void read(int &in) {
int c,symbol=;
while(isspace(c=IO::getchar()));
if(c=='-') { in=;symbol=-; }
else in=c-'';
while(isdigit(c=IO::getchar())) { in*=;in+=c-''; }
in*=symbol;
}
inline int read() { static int x;read(x);return x; }
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
#define PA(name,init,len) cout<<#name"["<<(len-init)<<"]=";FOR(_,init,len) cout<<name[_]<<" \n"[_==(len-1)];
#define Pa(name,init,len) cout<<#name"["<<(len-init+1)<<"]=";For(_,init,len) cout<<name[_]<<" \n"[_==(len)];
#define PV(name) cout<<#name"="<<name<<'\n'; const ll mod =1e9+;
struct Matrix{
ll d[][];
Matrix(){memset(d,,sizeof(d));}
Matrix operator*(const Matrix &rhs)const{
Matrix ret;
for(int i=;i<;++i) for(int j=;j<;++j) {for(int k=;k<;++k) ret.d[i][j]+=d[i][k]*rhs.d[k][j]%mod;ret.d[i][j]%=mod;}
return ret;
}
Matrix operator+(const Matrix &rhs)const{
Matrix ret;
FOR(i,,) FOR(j,,){
ret.d[i][j]=d[i][j]+rhs.d[i][j];
if(ret.d[i][j]>mod) ret.d[i][j]-=mod;
}
return ret;
}
void print(){
FOR(i,,) FOR(j,,) printf("%lld%c",d[i][j],j==?'\n':' ');
}
}; Matrix qpow(int n){
Matrix a,ret;
a.d[][]=a.d[][]=a.d[][]=a.d[][]=;
ret.d[][]=ret.d[][]=ret.d[][]=;
while(n){
if(n&) ret=a*ret;
n>>=;
a=a*a;
}
return ret;
} int main() {
#ifdef MengLan
int Beginning=clock();
//freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif // MengLan int T;scanf("%d",&T);
while(T--){
int n;scanf("%d",&n);
if(n<=) puts("");
else{
auto ans=qpow(n-);
printf("%lld\n",(ans.d[][]%mod+mod)%mod);
}
} #ifdef MengLan
printf("Time: %d\n",clock()-Beginning);
system("pause");
#endif // MengLan
return ;
}

Problem 3 虫洞(holes.cpp/c/pas)

【题目描述】

N个虫洞,M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。

1.从白洞跃迁到黑洞,消耗的燃料值减少delta,若该条路径消耗的燃料值变为负数的话,取为0。

2.从黑洞跃迁到白洞,消耗的燃料值增加delta。

3.路径两端均为黑洞或白洞,消耗的燃料值不变化。

作为压轴题,自然不会是如此简单的最短路问题,所以每过1单位时间黑洞变为白洞,白洞变为黑洞。在飞行过程中,可以选择在一个虫洞停留1个单位时间,如果当前为白洞,则不消耗燃料,否则消耗s[i]的燃料。现在请你求出从虫洞1到N最少的燃料消耗,保证一定存在1到N的路线。

【输入格式】

第1行:2个正整数N,M

第2行:N个整数,第i个为0表示虫洞i开始时为白洞,1表示黑洞。

第3行:N个整数,第i个数表示虫洞i的质量w[i]。

第4行:N个整数,第i个数表示在虫洞i停留消耗的燃料s[i]。

第5..M+4行:每行3个整数,u,v,k,表示在没有影响的情况下,从虫洞u到虫洞v需要消耗燃料k。

【输出格式】

一个整数,表示最少的燃料消耗。

【样例输入】

4 5

1 0 1 0

10 10 100 10

5 20 15 10

1 2 30

2 3 40

1 3 20

1 4 200

3 4 200

【样例输出】

130

【数据范围】

对于30%的数据: 1<=N<=100,1<=M<=500

对于60%的数据: 1<=N<=1000,1<=M<=5000

对于100%的数据: 1<=N<=5000,1<=M<=30000

其中20%的数据为1<=N<=3000的链

1<=u,v<=N, 1<=k,w[i],s[i]<=200

【样例说明】

按照1->3->4的路线。

既然题目都说了这是一道最短路问题,那么这就是一道最短路问题了(雾),再加上边权值>=0,那么理论上用dijkstra的优先度是比SPFA高的;

那么问题只在于怎么建边了;

首先,虫洞分黑洞白洞,并且在这两种状态中转换,那么如何去区分黑洞白洞呢?

拆点吧,把一个虫洞在黑洞和白洞的时候分别用一个点表示,本人习惯用i和i+n,还有一种常见的是i*2和i*2+1,可以使用位运算i<<1和i<<1|1表示;

以下使用点i和i+n表示同一个虫洞的两种状态;

题目有个要求,每隔1单位时间,虫洞将从黑洞变成白洞或从白洞变成黑洞;

那么对于两种操作:

1.从任意一个虫洞到另一个虫洞,需要1单位时间,假设A是白洞,B是黑洞,从A->B,则抵达时B应该为白洞状态,那么假设i是A白洞状态的点,i+n是A黑洞状态时的点,j是B黑洞状态时的点,j+n是B白洞状态时的点,那么将建边i->j+n,费用为C1和i+n->j,费用为C2;

2.可以在一个虫洞停留1单位时间,那么就是在虫洞在黑洞和白洞状态各向对方连一条单向边,假设虫洞的两个点分别为i和i+n,那么将建边i->i+n,费用为C1,i+n->i,费用为C2;

以上费用C按题意要求计算;

对于i和i+n与黑洞和白洞对应的方式有两种,

第一种将i与题目输入的白洞黑洞对应,那么i+n就为另一种,这样的好处是对于题目输入的边u->v,建边肯定是u->v+n和u+n->v,关键在于费用C的计算;

第二种将i直接与白洞对应,i+n直接与黑洞对应,那么这样需要判断输入的边u->v中u,v的状态是否相同,好处是相同的话,费用肯定都是k,不相同的话,一个费用是k-Δ,另一个是k+Δ;

本题贴两份代码,第一份是我的,拆点方式为i和i+n,对应方式为按输入对应(第一种),最短路用dijkstra

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<utility>
#include<numeric>
#include<iterator>
#include<algorithm>
#include<functional>
#include<ctime>
#include<cassert>
using std::cin;
using std::cout;
using std::endl;
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
#define FOR(i,init,len) for(int i=(init);i<(len);++i)
#define For(i,init,len) for(int i=(init);i<=(len);++i)
#define fi first
#define se second
#define pb push_back
#define is insert
namespace IO {
inline char getchar() {
static const int BUFSIZE=;
static char buf[BUFSIZE],*begin,*end;
if(begin==end) {
begin=buf;
end=buf+fread(buf,,BUFSIZE,stdin);
if(begin==end) return -;
}
return *begin++;
}
}
inline void read(int &in) {
int c,symbol=;
while(isspace(c=IO::getchar()));
if(c=='-') { in=;symbol=-; }
else in=c-'';
while(isdigit(c=IO::getchar())) { in*=;in+=c-''; }
in*=symbol;
}
inline int read() { static int x;read(x);return x; }
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
#define PA(name,init,len) cout<<#name"["<<(len-init)<<"]=";FOR(_,init,len) cout<<name[_]<<" \n"[_==(len-1)];
#define Pa(name,init,len) cout<<#name"["<<(len-init+1)<<"]=";For(_,init,len) cout<<name[_]<<" \n"[_==(len)];
#define PV(name) cout<<#name"="<<name<<'\n'; struct Edge{
int to,cost;
Edge(int to=,int cost=):to(to),cost(cost){}
};
const int maxn=6e4+;
std::vector<Edge> G[maxn];
int n,m;
int col[maxn],w[maxn],s[maxn]; struct Lan{
int u,cost;
Lan(int u=,int cost=):u(u),cost(cost){}
bool operator<(const Lan &rhs)const{return cost>rhs.cost;}
}; const int INF=1e9;
bool vis[maxn];
int d[maxn];
int dijkstra(){
std::priority_queue<Lan> q;
q.push(Lan(,));
For(i,,n+n) d[i]=INF;d[]=;
while(!q.empty()){
auto x=q.top();q.pop();
//printf("u:%d cost:%d\n",x.u,x.cost);
if(x.u==n||x.u==n+n) return x.cost;
if(vis[x.u]) continue;
vis[x.u]=true;
for(auto &y:G[x.u]) if(d[y.to]>d[x.u]+y.cost){
d[y.to]=d[x.u]+y.cost;
q.push(Lan(y.to,d[y.to]));
}
}
return -;
} int main() {
#ifdef MengLan
int Beginning=clock();
//freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif // MengLan scanf("%d%d",&n,&m);
For(i,,n) scanf("%d",col+i),col[i+n]=!col[i];
For(i,,n) scanf("%d",w+i),w[i+n]=w[i];
For(i,,n) scanf("%d",s+i);
For(i,,n) {
if(col[i]) G[i].pb(Edge(i+n,s[i])),G[i+n].pb(Edge(i,));
else G[i].pb(Edge(i+n,)),G[i+n].pb(Edge(i,s[i]));
}
For(i,,m){
int u,v,k;scanf("%d%d%d",&u,&v,&k);
int k1=k,k2=k;
if(!col[u]&&col[v]) k1=k-std::abs(w[u]-w[v]),k2=k+std::abs(w[u]-w[v]);
if(col[u]&&!col[v]) k1=k+std::abs(w[u]-w[v]),k2=k-std::abs(w[u]-w[v]);
if(k1<) k1=;
if(k2<) k2=;
G[u].pb(Edge(v+n,k1));
G[u+n].pb(Edge(v,k2));
}
//For(i,1,n+n) for(auto &y:G[i]) printf("u:%d v:%d c:%d\n",i,y.to,y.cost);
printf("%d\n",dijkstra()); #ifdef MengLan
printf("Time: %d\n",clock()-Beginning);
system("pause");
#endif // MengLan
return ;
}

第二份代码为标程,拆点方式为i*2-1和i*2,对应方式为第二种,最短路算法用SPFA

#include<cstdio>
#include<cstring>
#define rep(i,n) for(int i=1;i<=n;i++)
#define abs(x) (x > 0 ? x : -(x))
const int maxn=,maxm=,maxq=;
int n,m,u,v,k,sz,l,r,x,delta,
p[maxn],w[maxn],d[maxn],q[maxq+],en[maxn],pre[maxm],g[maxm],len[maxm];
bool Inq[maxn];
inline void Ins(int u,int v,int d)
{
pre[++sz]=en[u];en[u]=sz;g[sz]=v;len[sz]=d;
}
void Init_And_Set_Map()
{
scanf("%d%d",&n,&m);
rep(i,n) scanf("%d",&p[i]);
rep(i,n) scanf("%d",&w[i]);
rep(i,n)
{
scanf("%d",&k);
Ins(i+i-,i+i,);
Ins(i+i,i+i-,k);
}
rep(i,m)
{
scanf("%d%d%d",&u,&v,&k);
if (p[u]==p[v])
{
Ins(u+u-,v+v,k);
Ins(u+u,v+v-,k);
}
else
{
delta=abs(w[u]-w[v]);
Ins(u+u-,v+v-, (k-delta> ? k-delta : ));
Ins(u+u,v+v, k+delta);
}
} }
void SPFA()
{
memset(d,0x7F,sizeof(d));
q[]=p[]+;d[q[]]=l=r=;
while ((r+&maxq) != l)
{
x=q[l];l=(l+)&maxq;Inq[x]=;
for(int i=en[x];i;i=pre[i])
{
v=g[i];
if (d[x]+len[i]<d[v])
{
d[v]=d[x]+len[i];
if (Inq[v]) continue;
Inq[v]=;
if (d[v]<d[q[l]]) q[l=(l-)&maxq]=v;
else q[r=(r+)&maxq]=v;
}
}
} }
int main()
{
freopen("holes.in","r",stdin);
freopen("holes.out","w",stdout);
Init_And_Set_Map();
SPFA();
printf("%d",d[n+n-]<d[n+n] ? d[n+n-] : d[n+n]);
return ;
}
上一篇:美国白宫开源“数据地图”,记录*在各地的工作


下一篇:centos7.2安装mysql5.7