noip历届签到题题解.doc

石头剪刀布 /2014/problem/3716/联合权值/problem/3728/无线网络发射器/problem/3578/寻找道路/problem/3731/石头剪刀布打表，找出对应关系。#include#include using namespace std;const int m55= 0,0,1,1,0, 1,0,0,1,0, 0,1,0,0,1, 0,0,1,0,1, 1,1,0,0,0, ;int a205,b205;int main() int n,na,nb; scanf(%d %d %d,&n,&na,&nb); for(int i=0;ina;i+) scanf(%d,&ai); for(int i=0;inb;i+) scanf(%d,&bi); int sa=0,sb=0; for(int i=0;in;i+) sa=sa+mai%nabi%nb; sb=sb+mbi%nbai%na; printf(%d %d,sa ,sb); return(0);联合权值#include #include #include #include using namespace std;long long n,p,k,w200010;bool vis200010;vector edge200010;void dfs(int x,int last1,int last2)visx=1;long long t=0,t2=0,t3=0,t4=0;for (int i=0;i=t3) t4=t3; t3=wy; if (wyn;for (int i=1;iuv;edgeu.push_back(v);edgev.push_back(u);for (int i=1;iwi;dfs(1,0,0); coutp k*2%10007endl;return 0;有关图的问题，到时候再解决。无线网络发射器#include#includeusing namespace std;int map200200;int d,n,x,y,a,fa;int main()long long ans=0;scanf(%d%d,&d,&n);for(int i=0;in;i+)scanf(%d%d%d,&x,&y,&a);mapxy=a;for(int i=0;i=128;i+)for(int j=0;j=128;j+)long long t=0;for(int u=i-d;u=i+d;u+)for(int v=j-d;v=0&u=0&v=128)t=t+mapuv;if(anst)ans=t;fa=1;elseif(t=ans)fa=fa+1;printf(%d %lld,fa,ans);return(0);暴力搜索，不解释。寻找道路先反向，搜出所有与终点相连接的点然后再删除所有已加边，正向再加一遍边搜一遍，只要有点的出边的出点为false（不与终点连通），它就为false（刚开始只要它与终点连通就true）然后再SPFAtrue的点就ok了DFS想直接搜出来符合条件的貌似不行.#include #include #include #include using namespace std;const int INF=999999;int n,m,s,t,g20000,tot,dis20000,q20000,a200100,b200100;bool vis20000,used20000,inq20000;struct edgeint t; int next;e500000;void addedge(int a,int b) tot+=1; etot.t=b; etot.next=ga; ga=tot;void dfss(int x)if(usedx)return;usedx=true;for(int i=gx;i;i=ei.next)if(!usedei.t)dfss(ei.t);void SPFA()memset(dis,INF,sizeof(dis);int head=0,tail=1;diss=0;qtail=s;inqs=true;while(head!=tail)head+=1;head=(head-1)%20000)+1;int x=qhead;inqx=false;for(int i=gx;i;i=ei.next)if(disei.tdisx+1&visei.t)/SPFA只走vis=true的点disei.t=disx+1;if(!inqei.t)tail+=1;tail=(tail-1)%20000)+1;qtail=ei.t;inqei.t=true;int main() scanf(%d%d,&n,&m); for(int i=1;i=m;i+) scanf(%d%d,&ai,&bi); addedge(bi,ai); scanf(%d%d,&s,&t); dfss(t);/先反向搜一遍，与终点不连通的不会被走到 if(!useds) printf(-1); else memset(e,0,sizeof(e);memset(g,0,sizeof(g);tot=0;for(int i=1;i=m;i+)addedge(ai,bi);/再正向+边，判断，若其有一个边的终点不与终点连通，即不符合，FALSEfor(int i=1;i=n;i+)if(usedi)visi=true;for(int j=gi;j;j=ej.next)if(!usedej.t)visi=false;SPFA();/SPFA只走vis=true的点 printf(%d,dist); return 0;转圈游戏 /2013/problem/3285/火柴排队/problem/3286/积木大赛/problem/3288/花匠/problem/3289/转圈#include#includeusing namespace std;int n,m,k,x;long long power(int a,int b,int mod)if(b=0) return 1;long long t=power(a,b/2,mod);t=(t*t)%mod;if(b%2)return (t*a)%mod;elsereturn (t);int main()scanf(%d%d%d%d,&n,&m,&k,&x);long long left=power(10,k,n)*m;left%=n;printf(%dn,(x+left)%n);return(0);游戏快速幂。火柴排队#include#include#includeusing namespace std;int d1000001;long long ans=0;void stablesort(int *a,int l,int mid,int r) int i=l,j=mid+1,k=l; while (i=mid & j=r) if (ai=aj) dk+=ai+; else dk+=aj+; ans+=mid+1-i;ans=ans%99999997; while (i=mid) dk+=ai+; while (j=r) dk+=aj+; for (int q=l;q=r;q+) aq=dq;void merge(int *a,int l,int r) if (lr) int mid=(l+r)/2; merge(a,l,mid); merge(a,mid+1,r); stablesort(a,l,mid,r); int n,c1000001;struct data int xx,yy;a1000001,b1000001;inline int cmp(const void *a,const void *b) if ( (*(data *)a) .xx (*(data *)b) . xx ) return 1; else return -1;int main() scanf(%d,&n); for (int q=0;qn;q+) scanf(%d,&aq.xx);aq.yy=q; for (int q=0;qn;q+) scanf(%d,&bq.xx);bq.yy=q; qsort(a,n,sizeof(data),cmp); qsort(b,n,sizeof(data),cmp); for (int q=0;qn;q+) cbq.yy=aq.yy; merge(c,0,n-1); printf(%d,ans); return 0;积木大赛 #include #include #include using namespace std;int n , first , next , ans;int i;int main() while( scanf( %d , &n