「CF325X」MemSQL start[c] up Round 1
A. Square and Rectangles
模拟题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define mod 1000000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n; ll mx=-inf,nx=inf,my=-inf,ny=inf,tot; int main() { n=read(); for(int i=1;i<=n;i++) { ll x1=read(),y1=read(),x2=read(),y2=read(); if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); tot+=(x2-x1)*(y2-y1); nx=min(nx,x1); mx=max(mx,x2); ny=min(ny,y1); my=max(my,y2); } if(tot==(mx-nx)*(my-ny)&&(mx-nx)==(my-ny))puts("YES"); else puts("NO"); return 0; } |
B. Stadium and Games
\[(2^k-1)m+m(m-1)/2=n\]
枚举k二分得出m
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define mod 1000000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } ll n; vector<ll>ans; ll check(ll t) { ll l=1,r=sqrt(2*n); if(t!=0)r=min(r,n/t); while(l<=r) { ll mid=(l+r)>>1; if(mid*(mid-1)/2+mid*t<n)l=mid+1; else r=mid-1; } if(l*(l-1)/2+l*t==n)return l; return 0; } int main() { n=read(); for(int k=0;;k++) { ll t=(1LL<<k)-1; if(t>n)break; ll tmp=check(t); if(tmp&&(tmp&1))ans.push_back(tmp*(t+1)); } if(ans.size()==0)puts("-1"); else { sort(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl; } return 0; } |
C. Monsters and Diamonds
此题比较恶心QAQ
求最短用个类似dijkstra的东西，如果一种u->{v}的转移所有mn[v]都确定了，把这个转移放进堆
或者是某个转移的代价被更新了
求最长用记忆化搜索，走出环就是inf
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pa pair<int,int> #define inf 1000000000 #define ansmx 314000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int m,n; int mn[100005],mx[100005]; bool vis[100005],inq[100005]; vector<int>u[100005],v[100005]; priority_queue<pa,vector<pa>,greater<pa> >q; struct data{ int id,w,r,sum; vector<int>v; }p[100005]; void dijkstra() { memset(mn,127,sizeof(mn)); while(!q.empty()) { int d=min(inf,q.top().first),x=q.top().second;q.pop(); if(d<mn[x]) { for(int i=0;i<v[x].size();i++) { int t=v[x][i]; if(mn[x]>inf)p[t].r--,p[t].sum+=d; else p[t].sum+=d-mn[x]; if(!p[t].r)q.push(make_pair(p[t].sum,p[t].id)); p[t].sum=min(p[t].sum,inf); } mn[x]=d; } } for(int i=1;i<=n;i++) if(mn[i]>inf)mn[i]=mx[i]=-1; } void dp(int x) { if(vis[x]||inq[x])return; vis[x]=inq[x]=1; for(int i=0;i<u[x].size();i++) { int t=u[x][i],sum=p[t].w; for(int j=0;j<p[t].v.size();j++) if(mx[p[t].v[j]]==-1){sum=-1;break;} if(sum==-1)continue; for(int j=0;j<p[t].v.size();j++) { int v=p[t].v[j]; dp(v); if(inq[v]||mx[v]==inf){sum=inf;break;} sum+=mx[v]; } mx[x]=max(mx[x],sum); } inq[x]=0; } int main() { m=read();n=read(); for(int i=1;i<=m;i++) { p[i].id=read();u[p[i].id].push_back(i); int x=read(),y; for(int j=1;j<=x;j++) { y=read(); if(y==-1)p[i].w++; else { p[i].r++; p[i].v.push_back(y);v[y].push_back(i); } } if(p[i].w==x)q.push(make_pair(p[i].w,p[i].id)); p[i].sum=p[i].w; } dijkstra(); for(int i=1;i<=n;i++) if(mx[i]!=-1&&!vis[i])dp(i); for(int i=1;i<=n;i++) if(mx[i]==inf)mx[i]=-2; for(int i=1;i<=n;i++) printf("%d %d\n",min(mn[i],ansmx),min(mx[i],ansmx)); return 0; } |
D. Reclamation
把图扩展成r*2*c, 增加(i,j)时，同时增加(i,j+c),若(i,j)到(i,j+c)存在一条路经，就有一条环形障碍切断路径
操作用带撤销的并查集实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define p(x,y) 2*(x-1)*m+y #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,K,ans; int xx[]={1,1,1,-1,-1,-1,0,0},yy[]={1,-1,0,1,-1,0,1,-1}; int mark[3005][6005]; int fa[18000005],size[18000005]; int u[25],v[25],top; int find(int x) { return x==fa[x]?x:find(fa[x]); } void merge(int x,int y) { if(x==y)return; if(size[x]>size[y])swap(x,y); fa[x]=y;size[y]+=size[x]; u[++top]=x;v[top]=y; } void add(int x,int y) { mark[x][y]=1; for(int k=0;k<8;k++) { int nx=x+xx[k],ny=y+yy[k]; if(ny<1)ny=2*m; if(ny>2*m)ny=1; if(mark[nx][ny])merge(find(p(x,y)),find(p(nx,ny))); } } int main() { n=read();m=read();K=read(); for(int i=1;i<=2*n*m;i++)fa[i]=i; for(int i=1;i<=2*n*m;i++)size[i]=1; while(K--) { int x=read(),y=read(); top=0; add(x,y);add(x,y+m); if(find(p(x,y))==find(p(x,y+m))) { mark[x][y]=mark[x][y+m]=0; while(top) { fa[u[top]]=u[top]; size[v[top]]-=size[u[top]]; top--; } } else ans++; } printf("%d\n",ans); return 0; } |
E. The Red Button
orz wmd神犇的题解
http://blog.csdn.net/wmdcstdio/article/details/44587751
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define mod 1000000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int m,n; bool vis[100005]; vector<int>ans; void dfs(int x) { vis[x]=1; if(!vis[2*x%n]) dfs(2*x%n); if(!vis[(2*x+1)%n]) dfs((2*x+1)%n); ans.push_back(x); } int main() { n=read(); if(n&1) puts("-1"); else { dfs(0); for(int i=ans.size()-1;i>=0;i--) printf("%d ",ans[i]); puts("0"); } return 0; } |
计数器 9325691
OI 课件=>
OI 课件=>
首页上一个大大的公式感觉好怪……