简要记录题解思路
f:battle City
bfs+优先队列
每次入队前进行标记,每次出队都上当前最短的路径
bfs+优先队列似乎就是dijkstra算法 ??code
char mp[maxm][maxn];int vis[maxm][maxn];//记录是否处理过struct node{ int x,y; int step; node(int x_,int y_,int s_):x(x_),y(y_),step(s_){}}; bool operator < (node a,node b){ return a.step>b.step; }int mv[4][2]={ {-1,0},{1,0},{0,-1},{0,1}};//优先队列int m,n;int bfs(node begin,int endx,int endy){ priority_queue que; vis[begin.x][begin.y]=1; que.push(begin); while(!que.empty()){ node tmp=que.top(); que.pop(); //printf("db %d %d step %d\n",tmp.x,tmp.y,tmp.step); if(tmp.x==endx&&tmp.y==endy) return tmp.step; int tmpx,tmpy,tmps; for(int i=0;i<4;i++){ tmpx=tmp.x+mv[i][0]; tmpy=tmp.y+mv[i][1]; if(tmpx<0||tmpx>=m||tmpy<0||tmpy>=n||vis[tmpx][tmpy]||mp[tmpx][tmpy]=='S'||mp[tmpx][tmpy]=='R') continue;//依旧可能出现相同坐标都在队列中 else if(mp[tmpx][tmpy]=='B') tmps=tmp.step+2; else tmps=tmp.step+1; node t=node(tmpx,tmpy,tmps); vis[tmpx][tmpy]=1; que.push(t); //else if(mp[tmpx][tmpy]=='B'){node t=node(tmpx,tmpy,tmp.step+2);vis[tmpx][tmpy]=1;que.push(t);} //else if(mp[tmpx][tmpy]=='E'||mp[tmpx][tmpy]=='T'){node t=node(tmpx,tmpy,tmp.step+1);vis[tmpx][tmpy]=1;que.push(t);} } } return -1;//no find}node beg=node(0,0,0);int endx,endy;int main(){ while(scanf("%d %d",&m,&n)&&m!=0){ //CL(mp,0); CL(vis,0); /* while(!que.empty()){ que.pop(); } */ for(int i=0;i g: 从N个数里找出和为N的倍数
数学题(鸽巢原理)+前缀和
处理前缀和的模N为0和相同的情况
code
void output(int i,int j){ printf("%d\n",j-i); for(int t=i+1;t<=j;t++){ printf("%d\n",a[t]); }}int main(){ scanf("%d",&n); //CL(tag,-1); bool flag=false;//是否已经找到该组数据答案 for(int i=1;i<=n;i++){ scanf("%d",a+i); if(flag) continue; sum[i]=a[i]; sum[i]+=sum[i-1]; int mod=sum[i]%n; if(mod==0){ output(0,i); flag=true; continue; } //printf("db %d %d mod %d tag[mod] %d\n",i,sum[i],mod,tag[mod]); if(tag[mod]==0){ tag[mod]=i; } else{ output(tag[mod],i); flag=true; } } return 0;} h :判断负环
bellman-ford
bellman-ford算法处理单源最短路(可以有负边),基本操作：
N-1次的松弛，每次松弛时对边<u,v> dis[v]=min(dis[v],dis[u]+cost(u,v)) 不优化的复杂度O(NE)code
struct Edge{ int u,v,w,next; //Edge(int u_,int v_,int w_):u(u_),v(v_),w(w_) {}}es[maxm];//maybe be not need uint head[maxn];//head[u]链表头，边编号int dis[maxn];//init -1int cnt;void add(int u,int v,int w){ es[cnt].u=u;es[cnt].v=v;es[cnt].w=w; es[cnt].next=head[u]; head[u]=cnt; cnt++;}void bellman(int s){ //原点s进行bellmanford算法 CL(dis,0x3f); dis[s]=0;// dis0 //dis1...dis(n-1) //dis(n)[j]=min(dis(n-1)[j],dis(n-1)[i]+cost[i][j]) for(int t=1;t<=n-1;t++){ //优化之一如果有一次都没更新则停止 //便利所有边 for(int j=0;j dis[u]+w) dis[v]=dis[u]+w;//更新 } }}bool check(){ //n-1次后还能更新则存在负环 for(int j=0;j dis[u]+w) return false; } return true;}int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d %d %d",&n,&m,&W); //初始化 cnt=0; CL(head,-1); int u,v,w; for(int i=0;i I:正方形(找出N个整点构成的正方形个数)
手写hash+简单几何关系
枚举两点，得到正方形的另外两点，hash检索(注意选模,搜索时时搜索自由区域才停)
注意枚举重复情况(4条边都被枚举遍)code
const int maxn=100007;struct point{ int x,y; int count;//标志有效位置}hash[100007];int n;int xx[1005],yy[1005];void tohash(int x,int y){ int pos=(x*x+y*y+x-y)%maxn; while(hash[pos].count!=0){ pos=(pos+1)%maxn; } hash[pos].count=1; hash[pos].x=x;hash[pos].y=y;}int search(int x,int y){ int pos=(x*x+y*y+x-y)%maxn; while(hash[pos].count!=0){ if(hash[pos].x==x&&hash[pos].y==y) return 1; pos=(pos+1)%maxn; } //printf("db search pos:%d x %d y %d\n",pos,x,y); //if(hash[pos].x==x&&hash[pos].y==y) return 1; return 0;}int main(){ while(scanf("%d",&n)&&n!=0){ CL(hash,0); int x,y; for(int i=0;i >2); } return 0;} j:container
给出三维整点左边，要将这些区域包裹起来的最小表面积
6n-2m ;n是点的个数，m是相接的面
但没找到原题，无法测试code
struct cell{ int x,y,z;}cels[maxn];int n;bool checkadj(cell c1,cell c2){ return (abs(c1.x-c1.x)+abs(c1.y-c2.y)+abs(c1.z-c2.z))<=1;//no same}int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=0;i