找了一些比较水的cf上的题目,然而又不想整套整套的的写了,于是一些散的cf上的题目就放在这里了。
现在做了几题:
30
好弱啊、、
427B.Prison Transfer
题意:给定长度为n的一个序列,和c,t两个数字。问你有多少个连续的长度为c的子串,且序列中最大数不超过t。
题解:直接扫一遍。
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 |
#include <bits/stdc++.h> #define maxn 200010 using namespace std; template <class T> inline void read(T &res){ char c;res=0; while((c=getchar())<'0'||c>'9'); while(c>='0'&&c<='9'){ res=res*10+(c-'0'); c=getchar(); } } ///////// int a[maxn]; int n,c,t; int main() { read(n);read(t);read(c); for(int i=1;i<=n;i++) read(a[i]); int ans=0,pos=0; for(int i=1;i<=n;i++){ if(a[i]>t) pos=0; else{ pos++; if(pos>=c) ans++; } } printf("%d\n",ans); } |
475B.Strongly Connected City
给出n条水平的单向道路,m条竖直的单向道路。问形成的n*m个节点是否都可以互相可达。
题解:tarjan求一下整个图是否为一个强连通分量。
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 |
#include <bits/stdc++.h> #define maxn 500 using namespace std; typedef long long ll; int n,m; vector<int>e[maxn]; int pre[maxn],low[maxn],dfs_clock,scc_cnt,sccno[maxn]; stack<int>S; void dfs(int st){ pre[st]=low[st]=(++dfs_clock); S.push(st); for(int i=0;i<e[st].size();i++){ int Next=e[st][i]; if(!pre[Next]){ dfs(Next); low[st]=min(low[st],low[Next]); } else if(!sccno[Next]){ low[st]=min(low[st],pre[Next]); } } if(low[st]==pre[st]){ scc_cnt++; while(1){ int now=S.top();S.pop(); sccno[now]=scc_cnt; if(now==st) break; } } } void Tarjan(){ dfs_clock=scc_cnt=0; memset(pre,0,sizeof(pre));memset(sccno,0,sizeof(sccno)); for(int i=1;i<=n*m;i++) if(!pre[i]) dfs(i); } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ char ch;scanf(" %c",&ch); if(ch=='<'){ for(int j=1;j<m;j++){ int u=(i-1)*m+j; int v=(i-1)*m+j+1; e[v].push_back(u); } } else if(ch=='>'){ for(int j=1;j<m;j++){ int u=(i-1)*m+j; int v=(i-1)*m+j+1; e[u].push_back(v); } } } for(int i=1;i<=m;i++){ char ch;scanf(" %c",&ch); if(ch=='^'){ for(int j=1;j<n;j++){ int u=(j-1)*m+i; int v=j*m+i; e[v].push_back(u); } } else if(ch=='v'){ for(int j=1;j<n;j++){ int u=(j-1)*m+i; int v=j*m+i; e[u].push_back(v); } } } Tarjan(); int flag=sccno[1]; bool ok=true; for(int i=2;i<=n*m;i++){ if(flag!=sccno[i]) ok=0; } if(ok) puts("YES"); else puts("NO"); } |
510C.Fox And Names
题意:给出n个字符串,问是否存在一个字母表,使得这n个字符串满足字典序。
题解:字典序其实就是一种拓扑关系。那么根据字符串的关系,判断是否可以建立一个拓扑图即可。
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 |
#include <bits/stdc++.h> #define maxn 30 using namespace std; typedef long long ll; vector<int>e[maxn]; int n; char ss[211][211]; int in[maxn],vis[maxn]; int ans[maxn]; bool toposort(){ queue<int>que; for(int i=1;i<=26;i++){ if(!in[i]){ vis[i]=1; que.push(i); } } int cnt=0; while(!que.empty()){ int now=que.front();que.pop(); ans[++cnt]=now; for(int i=0;i<e[now].size();i++){ in[e[now][i]]--; if(in[e[now][i]]==0&&vis[e[now][i]]==0){ vis[e[now][i]]=1; que.push(e[now][i]); } } } for(int i=1;i<=26;i++) if(!vis[i]) return 1; return 0; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf(" %s",ss[i]); bool flag=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ int len1=strlen(ss[i]);int len2=strlen(ss[j]); for(int k=0;k<len1;k++){ if(k>len2-1) {flag=1;break;} if(ss[i][k]!=ss[j][k]){ int u=ss[i][k]-'a'+1; int v=ss[j][k]-'a'+1; e[u].push_back(v); in[v]++;break; } } } if(flag) break; } if(!flag) flag=toposort(); if(flag) puts("Impossible"); else { for(int i=1;i<=26;i++) printf("%c",(char)(ans[i]+'a'-1)); puts(""); } } |
437C.The Child and Toy
题意:给出n个节点,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 |
#include <bits/stdc++.h> #define maxn 1050 using namespace std; typedef long long ll; template <class T> inline void read(T &res){ char c;res=0; while((c=getchar())<'0'||c>'9'); while(c>='0'&&c<='9'){ res=res*10+(c-'0'); c=getchar(); } } //////// int n,m; bool des[maxn]; struct P{ int val,id; P(){} P(int _x,int _y):val(_x),id(_y){} }pp[maxn]; bool cmp(const P& a,const P& b){ return a.val<b.val; } int ma[maxn]; vector<int>e[maxn]; int main() { read(n);read(m); for(int i=1;i<=n;i++) { read(pp[i].val),pp[i].id=i; ma[i]=pp[i].val; } sort(pp+1,pp+1+n,cmp); for(int i=1;i<=m;i++){ int u,v;read(u);read(v); e[u].push_back(v); e[v].push_back(u); } ll ans=0; for(int i=n;i;i--){ int pos=pp[i].id; des[pos]=1; for(int j=0;j<e[pos].size();j++){ if(des[e[pos][j]]) continue; ans+=ma[e[pos][j]]; } } printf("%I64d\n",ans); } |
500A.New Year Transportation
题意:有n个城市1排,从第i个城市可以走到i+a[i]号城市,给一个城市t,问是否能从1到t?
题解:从1开始扫一遍打标记,比如i打上标记,那么i+a[i]也打上标记。看最后t有没有被打上标记即可。
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 |
#include <bits/stdc++.h> using namespace std; typedef long long ll; template <class T> inline void read(T &res){ char c;res=0; while((c=getchar())<'0'||c>'9'); while(c>='0'&&c<='9'){ res=res*10+(c-'0'); c=getchar(); } } ////// int a[30100]; bool vis[30100]; int main() { int n,t;read(n);read(t); for(int i=1;i<n;i++) read(a[i]); vis[1]=1; for(int i=1;i<=n;i++){ if(vis[i]) vis[i+a[i]]=1; } if(vis[t]) puts("YES"); else puts("NO"); } |
519B. A and B and Compilation Errors(模拟)
题意:给出三个序列下面的序列是上面的序列去掉一个数得到的。求出两个去掉的数。
煞笔题。。
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 |
#include <bits/stdc++.h> using namespace std; typedef long long ll; template <class T> inline void read(T &res){ char c;res=0; while((c=getchar())<'0'||c>'9'); while(c>='0'&&c<='9'){ res=res*10+(c-'0'); c=getchar(); } } ///// typedef long long ll; ll sum1,sum2,sum3; int main() { int n;read(n); for(int i=1;i<=n;i++){ int tmp;read(tmp);sum1+=(ll)tmp; } for(int i=1;i<=n-1;i++){ int tmp;read(tmp);sum2+=(ll)tmp; } for(int i=1;i<=n-2;i++){ int tmp;read(tmp);sum3+=(ll)tmp; } printf("%I64d\n",sum1-sum2); printf("%I64d\n",sum2-sum3); } |
639B. Bear and Forgotten Tree 3(构造乱搞)
题意:构造一棵个节点,直径为
,深度为
的树(深度是从1号节点算起)。
题解:判掉一些无解的情况。对于合法的的情况先从1连一条长度为h的链,然后再从1连一条长度为d-h的链,最后把剩下的点都连到根上。(这里有一个坑,如果h=d的话不能连1号节点)。细节挺多的,直接上代码了。
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 |
#include <bits/stdc++.h> #define maxn 100010 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; template <class T> inline void read(T &res){ char c;res=0; while((c=getchar())<'0'||c>'9'); while(c>='0'&&c<='9'){ res=res*10+(c-'0'); c=getchar(); } } /////// int n,d,h; int fa[maxn]; int main() { read(n);read(d);read(h); if(n<d+1||2*h+1<d+1||d+1<h+1||(d==1&&n>2)) {puts("-1");return 0;} for(int i=2;i<=h+1;i++) fa[i]=i-1; if(d==h) for(int i=d+2;i<=n;i++) fa[i]=2; else { fa[h+2]=1; for(int i=h+3;i<=d+1;i++) fa[i]=i-1; for(int i=d+2;i<=n;i++) fa[i]=1; } for(int i=n;i>1;i--) printf("%d %d\n",fa[i],i); } |
298A. Snow Footprints(模拟+分类讨论)
题意不想说了。。。
只会出现RRLL,RRRR,LLLL这样的序列。而且注意是跨过这个格子,才会留下脚印。然后分类讨论一下。。。做这种字符串的分类讨论题目太恶心了。。。
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 |
#include <bits/stdc++.h> #define maxn 1005 using namespace std; char s[maxn]; int main() { int n;scanf("%d",&n); scanf("%s",s+1); int flags=0,flagt=0; int ss=0,t=0; for(int i=1;i<=n;i++){ if(flags&&s[i]=='R'&&s[i+1]=='.'){ t=i+1; break; } if(s[i]=='R'&&s[i+1]=='L'){ t=i;flagt=1; } if(s[i]=='R'&&flags==0){ flags=1; ss=i; } if(s[i]=='.'&&flags&&(!flagt)){ t=i; break; } if(s[i]=='L'&&flagt==0){ flagt=1; t=i-1; } if(s[i]=='.'&&flagt&&(!flags)){ ss=i-1; break; } } cout<<ss<<" "<<t<<endl; } |
298B. Sail(模拟+贪心)
题意不想说了。
显然对于当前位置,在一个时刻只有跟着风向走还是不走这两种选择。那么肯定要选择可以让我们离终点更近的选择了。把整个过程模拟一遍。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <bits/stdc++.h> #define maxn 100005 #define inf 0x3f3f3f3f using namespace std; char s[maxn]; int main() { int t,sx,sy,ex,ey; scanf("%d %d %d %d %d",&t,&sx,&sy,&ex,&ey); scanf(" %s",s+1); int flag=-1; for(int i=1;i<=t;i++){ if(s[i]=='S'&&sy>ey) sy-=1; if(s[i]=='E'&&sx<ex) sx+=1; if(s[i]=='W'&&sx>ex) sx-=1; if(s[i]=='N'&&sy<ey) sy+=1; if(sx==ex&&sy==ey) { printf("%d\n",i);break; } } if(sx!=ex||sy!=ey) puts("-1"); } |
382C. Arithmetic Progression(分类讨论)
题意:给出一个长度为n(n<1e5)的正数序列,每个数不超过1e8,然后你现在可以加入一个数让整个数列变成等差数列。有无数种方案输出-1,无解输出0.别的话输出方案数,以及添加的数。添加的数可以超过1e8或者是负数。
还是分类讨论。。。太恶心了。我们先计算出原数列的间距个数,以及间距大小。
1.如果只有一个数字,那么有无穷多解。
2.如果有三个或者以上间距一定无解。
3.只有一个间距的话。如果间距为0,也就是所有数都相同,那么只有一种方案。如果间距不为0而且这个序列的长度为2而且这个间距可以被2整除,那么有三种方案(因为可以放到中间)。否则只有两种。
4.有两个间距。如果较大的那个间距是较小的那个的两倍,较小的间距不能为0.而且较大间距的个数只有1个,那么有1种方案。
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 |
#include <bits/stdc++.h> using namespace std; int n; int a[100010]; map<int,int>ma; int cnt[100010]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); if(n==1) {puts("-1");return 0;} int pos=0; for(int i=2;i<=n;i++){ if(ma[a[i]-a[i-1]]==0){ ma[a[i]-a[i-1]]++; pos++; cnt[pos]=a[i]-a[i-1]; } else ma[a[i]-a[i-1]]++; } if(pos>=3) {puts("0");return 0;} if(pos==2){ int tmp=cnt[1];int tmp2=cnt[2]; if(tmp2<tmp) swap(tmp,tmp2); if(tmp==0) {puts("0");return 0;} if(tmp2%tmp==0&&tmp2/tmp==2&&ma[tmp2]==1){ printf("1\n"); for(int i=2;i<=n;i++){ if(a[i]-a[i-1]==tmp2){ printf("%d\n",a[i-1]+tmp2/2); } } } else puts("0"); } if(pos==1){ if(cnt[pos]==0) { puts("1"); printf("%d\n",a[1]); return 0; } if(n==2){ if(cnt[pos]%2==0){ printf("3\n"); printf("%d %d %d\n",a[1]-cnt[pos],a[1]+cnt[pos]/2,a[2]+cnt[pos]); } else { puts("2"); printf("%d %d\n",a[1]-cnt[pos],a[2]+cnt[pos]); } } else { puts("2"); printf("%d %d\n",a[1]-cnt[pos],a[n]+cnt[pos]); } } } |
450D. Jzzhu and Cities(最短路)
题目大意:在一个国家中有n个城市(城市编号1~n),m条公路,k条铁路,编号为1的城市为首都,为了节约,不需要的铁路需要关闭,问在保证首都到其余所有城市的最短路不变的条件下,最多有多少条铁路是不需要的。
首先我们可以跑一遍单源最短路(最好dij,spfa的用优先队列卡过去)。然后我们枚举火车线路,如果端点的最短路径大于火车线路,那么肯定要删除。如果端点的最短路径等于火车线路,且最短路径条数大于1,那么也要删除。
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 |
#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define maxn 100010 using namespace std; typedef long long ll; typedef pair<long,int> pii; template <class T> inline void read(T &res){ char c;res=0; while((c=getchar())<'0'||c>'9'); while(c>='0'&&c<='9'){ res=res*10+(c-'0'); c=getchar(); } } /////// struct edge{ int to; ll cost; edge(){} edge(int _to,ll _cost):to(_to),cost(_cost) {} }; int n,m,k; vector<edge>e[maxn]; ll dis[maxn]; int qaq[maxn]; edge train[maxn]; int vis[maxn],from[maxn]; void dijkstra(int st){ memset(dis,inf,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(from,0,sizeof(0)); priority_queue< pii,vector< pii >,greater< pii > > que; que.push(make_pair(0,1)); dis[st]=0; while(!que.empty()){ pii now=que.top();que.pop(); int x=now.second; if(vis[x]) continue; vis[x]=1; for(int i=0;i<e[x].size();i++){ int Next=e[x][i].to;int len=e[x][i].cost; if(dis[x]+len<dis[Next]){ dis[Next]=dis[x]+len; from[Next]=1; que.push(make_pair(dis[Next],Next)); } else if(dis[x]+len==dis[Next]) from[Next]++; } } } int ans; int main() { read(n);read(m);read(k); for(int i=1;i<=m;i++){ int u,v,len; scanf("%d %d %d",&u,&v,&len); e[u].push_back(edge(v,len)); e[v].push_back(edge(u,len)); } int cnt=1; for(int i=1;i<=k;i++){ int v,len;scanf("%d %d",&v,&len); if(qaq[v]<=len&&qaq[v]) {ans++;continue;} e[1].push_back(edge(v,len)); qaq[v]=len; train[cnt++]=edge(v,len); } dijkstra(1); for(int i=1;i<cnt;i++){ if(dis[train[i].to]<train[i].cost) ans++; else if(dis[train[i].to]==train[i].cost&&from[train[i].to]>1){ from[train[i].to]--; ans++; } } printf("%d\n",ans); } |
451E.Devu and Flowers(组合数学)
题意:有n个盒子,从这n个盒子中选s支花(有的盒子可以不选),每个花坛有f[i]支花,同一个花坛的花颜色相同,不同花坛的花颜色不同,问说可以有多少种方案数。
如果没有f[i]的限制,那么题目相当于问的方案数。那么很明显由隔板法得到方案数为
。对于这个题目很明显这个答案会包括超过某些f[i]的答案。发现n才20,所以我们可以枚举一下超过的花坛有哪些组合,然后用容斥原理算出答案。注意如果某次超出的花坛为i,那么相当于把
这个式子右边的s减去一个f[i]+1再做插板法。因为模数很大,而项数很小,所以不用lucas,直接循环算出组合数即可。
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 |
#include <bits/stdc++.h> #define mod 1000000007 #define maxn 23 using namespace std; typedef long long ll; ll n,s; ll quick_pow(ll a,ll k) { ll res=1LL; while(k){ if(k&1) res=(res*a)%mod; k>>=1; a=(a*a)%mod; } return res; } ll C(ll n,ll m) { if(n<m) return 0; ll dis=max(n-m,m); ll cnt=min(n-m,m); ll fact1=1LL,fact2=1LL; for(int i=1;i<=cnt;i++) { fact1=fact1*(((ll)i+dis)%mod)%mod;fact2=fact2%mod*(ll)i%mod; } ll res=(fact1%mod*quick_pow(fact2,mod-2)%mod)%mod; return res; } ll f[maxn]; int main() { scanf("%I64d %I64d",&n,&s); for(int i=0;i<n;i++) scanf("%I64d",&f[i]); int maxx=((1<<n)-1); ll ans=0; for(int i=0;i<=maxx;i++){ ll sum=0;int flag=1; for(int j=0;j<n;j++){ if(i&(1<<j)){ flag=-flag; sum+=(f[j]+1LL); } } if(sum>s) continue; ans=(ans+flag*C(s-sum+n-1,n-1)+mod)%mod; } printf("%I64d\n",ans); } |
382A. Ksenia and Pan Scales
给出两个字符串S和T。S串中以’|’为分隔符,分成两部分。问你是否可以通过把T全部分成两部分(可以为空)分别给S中的两部分,让他们长度变得相同。
字符串模拟一下,用substr实在是方便。
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 |
#include <bits/stdc++.h> using namespace std; string s,t; int main() { cin>>s>>t; int len1=s.length();int len2=t.length(); int p=0; for(int i=0;i<len1;i++){ if(s[i]=='|') p=i; } int q=len1-1-p; string a=s.substr(0,p); string b; if(p==len1-1) b=""; else b=s.substr(p+1,len1); if(p==q){ if(len2%2) {puts("Impossible");return 0;} else { int pp=len2/2; cout<<a<<t.substr(0,pp)<<"|"<<b<<t.substr(pp,len2)<<endl; } } else { if((len2+len1-1)%2||p>len2+q||p+len2<q) {puts("Impossible");return 0;} else{ int len=(len1-1+len2)/2; cout<<a<<t.substr(0,len-p)<<"|"<<b<<t.substr(len-p,len2)<<endl; } } } |
543B. Destroying Roads
给出N个点和M条边,每条边的边权为1。给出S1,T1,len1,S2,T2,len2.问现在最多删去多少条边,可以让S1到T1的距离不超过len1,从S2到T2的距离不超过len2。
,
思路:把问题转化成至少有多少条边才可以满足让S1到T1的距离不超过len1,从S2到T2的距离不超过len2。假设我们找到了S1到T1的最短距离为dis1,S2到T2的最短距离为dis2。假设这两段最短路之间没有公共部分,那答案就是dis1+dis2。如果两段路径中间有重叠部分的话,我们可以通过枚举来得到答案。通过bfs暴力预处理出每个点对之间的最短距离,枚举就是O(1)的了。
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 |
#include <bits/stdc++.h> #define maxn 3333 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; int n,m,s1,t1,len1,s2,t2,len2; int dis[maxn][maxn]; int vis[maxn]; vector<int>e[maxn]; void bfs(int st){ memset(vis,0,sizeof(vis)); queue<int>que;vis[st]=1;que.push(st);dis[st][st]=0; while(!que.empty()){ int now=que.front();que.pop(); int Size=e[now].size(); vis[now]=1; for(int i=0;i<Size;++i){ if(vis[e[now][i]]) continue; if(dis[st][e[now][i]]>dis[st][now]+1) dis[st][e[now][i]]=dis[st][now]+1; que.push(e[now][i]); } } } int main() { memset(dis,inf,sizeof(dis)); scanf("%d %d",&n,&m); for(int i=1;i<=m;i++){ int u,v;scanf("%d %d",&u,&v); e[u].push_back(v); e[v].push_back(u); } scanf("%d %d %d",&s1,&t1,&len1); scanf("%d %d %d",&s2,&t2,&len2); for(int i=1;i<=n;i++) bfs(i); if(dis[s1][t1]>len1||dis[s2][t2]>len2) {puts("-1");return 0;} int ans=dis[s1][t1]+dis[s2][t2]; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(dis[s1][i]+dis[i][j]+dis[j][t1]<=len1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=len2) ans=min(ans,dis[s1][i]+dis[i][j]+dis[j][t1]+dis[s2][i]+dis[j][t2]); if(dis[s1][j]+dis[i][j]+dis[i][t1]<=len1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=len2) ans=min(ans,dis[s1][j]+dis[i][j]+dis[i][t1]+dis[s2][i]+dis[j][t2]); } } printf("%d\n",m-ans); } |
623A. Graph and String
题意:给出一个n(n<=500)个结点的无向图,每个结点标号”abc”三个字母其中一个。将标号为相同字母的结点连边,将所有标号为b的结点与其它标号的结点连边。给出图的m个连边,求一种合法的标号方案,不存在输出’NO’。
一个b标号的点肯定是和其余点都相连的,我们先把这样的点标上b。然后枚举剩余的点以及他们的相连情况,假设我们枚举到了的还没标号的点都标上’a’,那么和它相连的没标号的就一定是’a’,不相邻的一定是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 |
#include <bits/stdc++.h> #define maxn 555 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; int n,m; int e[maxn][maxn]; int du[maxn],color[maxn]; int a,b,c; int main() { memset(color,-1,sizeof(color)); scanf("%d %d",&n,&m); for(int i=1;i<=m;++i) { int u,v;scanf("%d %d",&u,&v); e[u][v]=e[v][u]=1; du[u]++;du[v]++; } a=0,b=0,c=0; for(int i=1;i<=n;++i) if(du[i]==n-1) {color[i]=1;b++;} for(int i=1;i<=n;++i){ if(color[i]==1) continue; if(color[i]==-1) {color[i]=0;a++;} for(int j=1;j<=n;++j){ if(color[j]==1||j==i) continue; if(!e[i][j]&&color[j]==-1) {color[j]=2-color[i];b++;} else if(e[i][j]&&color[j]==-1) {color[j]=color[i];a++;} else{ if(color[j]==color[i]&&(!e[i][j])) {puts("No");return 0;} if(color[j]!=color[i]&&(e[i][j])) {puts("No");return 0;} } } } if(a+b+c!=n) {puts("No");return 0;} bool flag=1; for(int i=1;i<=n;++i){ if(color[i]==2) if(du[i]!=b+c-1) {flag=0;break;} if(color[i]==1) if(du[i]!=b+a-1) {flag=0;break;} } if(!flag) puts("No"); else{ puts("Yes"); for(int i=1;i<=n;++i){ if(color[i]==2) printf("%c",'c'); if(color[i]==1) printf("%c",'b'); if(color[i]==0) printf("%c",'a'); } puts(""); } } |
650A. Watchmen
给定二维平面的n个坐标,求满足|xi−xj|+|yi−yj|=sqrt((xi−xj)∗(xi−xj)+(yi−yj)∗(yi−yj))的点对数
1≤n≤1e5,1≤xi,yi≤1e9,存在重复点的情况。
发现曼哈顿距离等于欧几里得距离,在二维平面上只有两点的x或者y相同才可能。所以用个map记录一下即可。但是因为有重点的存在,两个重点会被多算一次(x和y各一次)。所以再开个map记录一下点的个数即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <bits/stdc++.h> #define maxn 200010 using namespace std; typedef long long ll; typedef pair<int,int> pii; pii c[maxn]; int n; map<int,int>x,y; map<pii,int>cnt; int main() { scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d %d",&c[i].first,&c[i].second); ll ans=0; for(int i=1;i<=n;++i){ ans+=x[c[i].first];ans+=y[c[i].second]; x[c[i].first]++;y[c[i].second]++; ans-=cnt[c[i]]; cnt[c[i]]++; } printf("%I64d\n",ans); } |
460C. Number of Ways
题意:给你n个数,让你要把序列分成连续的三部分,要求每一部分的和相等。n<=1e5
预处理前缀和,然后扫一遍前缀和,开一个数组记录每个i之前(包括i在内)有多少个前缀和为sum/3的。然后倒着扫一遍后缀和,发现一个为sum/3的后缀和的时候,我们需要知道在i-2的位置及之前有多少个前缀和为sum/3的。因为要保证每一部分都不为空。
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 |
#include <bits/stdc++.h> #define maxn 500010 using namespace std; typedef long long ll; int n,a[maxn]; int cnt[maxn]; ll sum; int main() { scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); sum+=a[i]; } if(sum%3) {puts("0");return 0;} ll tmp=0,num=0; for(int i=1;i<=n-1;i++){ tmp+=a[i]; if(tmp==sum/3) num++; cnt[i]=num; } ll ans=0;tmp=0; for(int i=n;i>=3;i--){ tmp+=a[i]; if(tmp==sum/3) ans+=cnt[i-2]; } printf("%I64d\n",ans); } |
229C. Triangles
POI原题啊,考虑反面就可以了。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <bits/stdc++.h> #define maxn 1000100 using namespace std; typedef long long ll; ll n,m; int du[maxn]; int main() { scanf("%I64d %I64d",&n,&m); for(int i=1;i<=m;i++){ int u,v;scanf("%d %d",&u,&v); du[u]++,du[v]++; } ll tot=n*(n-1)*(n-2)/6; ll cnt=0; for(int i=1;i<=n;i++) cnt=cnt+(ll)du[i]*(n-1-du[i]); printf("%I64d\n",tot-cnt/2); } |
472A. Design Tutorial: Learn from Math
题意:给出一个n(),让你把它分成两个合数之和。
首先这个肯定是可以的。对于奇数的话,拆成9和n-9,因为n-9一定是偶数且大于2,所以这两个一定是两个合数。对于偶数的话,拆成8和n-8,因为n-8是偶数,所以这两个一定是合数。当然这是题解的证明,我们直接预处理出素数表,暴力枚举即可。
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 |
#include <bits/stdc++.h> using namespace std; int prime[1000005]; bool isprime[1000005]; int numprime; void getprime() { memset(prime,0,sizeof(prime)); memset(isprime,true,sizeof(isprime)); isprime[1]=0,isprime[0]=1; for(int i=2;i<=1000000;i++){ if(isprime[i]) prime[numprime++]=i; for(int j=0;j<numprime&&prime[j]*i<=1000000;j++){ isprime[prime[j]*i]=false; if(i%prime[j]==0) break; } } } int n; int main() { int i,j; getprime(); scanf("%d",&n); for(i=4;i<=n/2+1;i++){ j=n-i; if(isprime[i]||isprime[j]) continue; else break; } printf("%d %d\n",i,j); } |
472B. Design Tutorial: Learn from Life
题意:在1楼有n个人准备乘坐电梯,电梯每次只能装k个人。如何安排能够使得电梯运送完所有人之后再次停回到1楼时所经过的路程最少。求出这个最小路程。
想了个贪心,我是这么想的,从需要去楼层越高的人开始装人。其实可以这么证明,假如人数n可以整除k,从小开始还是从大开始都无所谓了,因为路程肯定确定了。但是在n不可以整除k的时候,就意味着最后有不足k人,那么这时候假如有人走最高层那肯定是比走较低层的路程大。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <bits/stdc++.h> #define maxn 2005 using namespace std; int n,k,f[maxn]; int main() { scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&f[i]); sort(f+1,f+1+n); int pos=n,ans=0; while(pos>=k){ ans+=2*(f[pos]-1); pos-=k; } if(pos) ans+=2*(f[pos]-1); printf("%d\n",ans); } |
472C. Design Tutorial: Make It Nondeterministic
题意:省略吧。。。。
我们按照题目给出的排列,来进行判断是否这个排列可行即可。贪心的扫一遍。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <bits/stdc++.h> #define maxn 100010 using namespace std; int n; string f[maxn],s[maxn]; int p[maxn]; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) cin>>f[i]>>s[i]; for(int i=1;i<=n;i++) cin>>p[i]; string now=min(f[p[1]],s[p[1]]);bool flag=1; for(int i=2;i<=n;i++){ if(f[p[i]]>now&&s[p[i]]>now) now=min(f[p[i]],s[p[i]]); else { if(f[p[i]]<now&&s[p[i]]<now) {flag=0;break;} else if(f[p[i]]<now) now=s[p[i]]; else now=f[p[i]]; } } if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } |
472D. Design Tutorial: Inverse the Problem
题意:给出一个n*n的矩阵(n<=2000),问你这个矩阵是否可能是一棵树的邻接矩阵。
额,一开始想的思路是把这个邻接矩阵求一个MST,这个MST就是那棵树了。然后再一一验证每对点之间的距离是否与邻接矩阵相同。但是这样的话可能需要一个LCA。。。不想写。。。后来问问韩司机,告诉我O(n^2)求一个MST就可以了。
我们先特判掉不符合邻接矩阵的情况,然后接下来对于每个点,都找到与它相邻最近的点为前驱,其实这就相当于求最小生成树的过程了。前驱也就相当于这棵树上的父亲,那么找到一个点u和他的前躯v后,我们再扫一下其余各点,这时候前驱v和该节点u到剩下的点的距离情况就两种了:dis[u]>dis[v]或者dis[u]<dis[v],而两者之间的差值一定是那条边的长度,否则就不合法。
时间复杂度O(n^2)。
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 |
#include <bits/stdc++.h> #define maxn 2005 using namespace std; int n; int a[maxn][maxn]; int main() { scanf("%d",&n);int flag=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((j==i&&a[i][j]!=0)||(j!=i&&a[i][j]==0)||a[i][j]!=a[j][i]) { flag=0;break; } if(!flag) {puts("NO");return 0;} for(int i=2;i<=n;i++){ int pre=1; for(int j=1;j<=n;j++){ if(i==j) continue; if(a[pre][i]>a[j][i]) pre=j; } for(int j=1;j<=n;j++){ if(i==j||j==pre) continue; if(abs(a[pre][j]-a[i][j])!=a[i][pre]) flag=0; } if(!flag) break; } if(flag) puts("YES"); else puts("NO"); } |
611C. New Year and Domino
题意:给出一个h*w(h,w均小于500)的字符矩阵,每次询问一个子矩阵,问其中可以放下一个1*2的骨牌的方案数。’#’不可以放置骨牌。
考虑维护二维前缀和,这样的话每次查询的时候可以在O(h+w)的时间内得到答案。计算的时候按照容斥就可以了。但是需要注意边界上的’.’可能需要减去一些方案。发现二维前缀和比较好的计算方法就是,先处理好第一行和第一列,然后容斥的计算剩余的部分。
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 |
#include <bits/stdc++.h> using namespace std; int h,w,q; char ma[555][555]; int sum[555][555]; int main() { scanf("%d %d",&h,&w);getchar(); for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++) scanf("%c",&ma[i][j]); getchar(); } for(int i=1;i<=h;i++) { if(ma[i][1]=='.'&&ma[i-1][1]=='.') sum[i][1]=sum[i-1][1]+1; else sum[i][1]=sum[i-1][1]; } for(int i=1;i<=w;i++) { if(ma[1][i]=='.'&&ma[1][i-1]=='.') sum[1][i]=sum[1][i-1]+1; else sum[1][i]=sum[1][i-1]; } for(int i=2;i<=h;i++){ for(int j=2;j<=w;j++){ if(ma[i][j]=='.'&&ma[i-1][j]=='.') sum[i][j]+=1; if(ma[i][j]=='.'&&ma[i][j-1]=='.') sum[i][j]+=1; sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; } } scanf("%d",&q); while(q--){ int r1,c1,r2,c2;scanf("%d %d %d %d",&r1,&c1,&r2,&c2); int ans=sum[r2][c2]-sum[r1-1][c2]-sum[r2][c1-1]+sum[r1-1][c1-1]; for(int i=r1;i<=r2;i++) if(ma[i][c1]=='.'&&ma[i][c1-1]=='.') ans--; for(int i=c1;i<=c2;i++) if(ma[r1][i]=='.'&&ma[r1-1][i]=='.') ans--; printf("%d\n",ans); } } |
4C. Registration system
哈希加上map计数。。。水题
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 |
#include <bits/stdc++.h> #define maxn 100010 #define inf 0x3f3f3f3f #define mod1 1000000007 #define mod2 998244353 #define H 233 using namespace std; typedef long long ll; typedef pair<int,int> pii; int n; map<pii,int>ma; int get_hash(char s[],int mod){ ll res=0;int len=strlen(s+1); for(int i=1;i<=len;i++) res=(res*H%mod+s[i])%mod; return res; } char s[35]; int main() { scanf("%d",&n); while(n--){ scanf(" %s",s+1); pii res=make_pair(get_hash(s,mod1),get_hash(s,mod2)); if(ma[res]) printf("%s%d\n",s+1,ma[res]); else puts("OK"); ma[res]++; } } |
732D. Exams
二分答案,然后贪心验证。贪心的思路是,每个考试科目肯定是越晚考越好,这样可以有更多的时间复习。所以保存下来每科的最晚考试时间,然后扫一遍,看每门是否可以在规定的最晚时间内完成即可。
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 |
#include <bits/stdc++.h> #define maxn 100010 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; int n,m,vis[maxn],a[maxn],d[maxn]; int day[maxn],last[maxn]; bool check(int mid){ int cnt=0; for(int i=mid;i;i--){ if(d[i]==0||vis[d[i]]==mid) continue; vis[d[i]]=mid; day[++cnt]=d[i]; last[d[i]]=i; } if(cnt!=m) return 0; ll pos=0; for(int i=m;i;i--){ if(pos+a[day[i]]<last[day[i]]) pos+=a[day[i]]+1LL; else return 0; } return 1; } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&d[i]); for(int j=1;j<=m;j++) scanf("%d",&a[j]); int L=1,R=n,ans=-1; while(L<=R){ int mid=((L+R)>>1); if(check(mid)){ ans=mid; R=mid-1; } else L=mid+1; } printf("%d\n",ans); } |
732E. Sockets
题意:略。
用map贪心乱搞了一通。因为s不超过1e9,所以每个电源最多被适配器操作31次就会变成0了。那么我们可以每个电源,按照从小到大的顺序,不断操作。当在computer里找到匹配的就标记一下。这样从小到大的顺序可以保证适配器数目最小。因为对于同一个可以被匹配的电脑,小的电源会先匹配上。
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 |
#include <bits/stdc++.h> #define maxn 200010 #define inf 0x3f3f3f3f #define mp make_pair using namespace std; typedef long long ll; typedef pair<int,int>pii; int n,m,ptos[maxn],cnt[maxn]; pii p[maxn],s[maxn]; map<pii,int>ma; int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&p[i].first); p[i].second=i; ma[p[i]]=-1; } sort(p+1,p+1+n); for(int i=1;i<=m;i++) { scanf("%d",&s[i].first); s[i].second=i; } sort(s+1,s+1+m); int ans1=0,ans2=0; for(int i=1;i<=m;i++){ int tmp=s[i].first; for(int j=0;j<=31;j++){ int pos=lower_bound(p+1,p+1+n,mp(tmp,0))-p; if(pos!=n+1&&p[pos].first==tmp&&ma[p[pos]]==-1){ ans1++;ans2+=j; ma[p[pos]]=i; ptos[p[pos].second]=s[i].second; p[pos].second=-1; cnt[s[i].second]=j; break; } tmp=ceil(1.0*tmp/2.0); } } cout<<ans1<<" "<<ans2<<endl; for(int i=1;i<=m;i++){ if(i!=1) printf(" "); printf("%d",cnt[i]); } puts(""); for(int i=1;i<=n;i++) { if(i!=1) printf(" "); printf("%d",ptos[i]); } puts(""); } |
732A. Buy a Shovel
随便搞搞。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <bits/stdc++.h> using namespace std; int k,r; int main() { scanf("%d %d",&k,&r); int i,tmp=k; if(k%10==r||k%10==0) {puts("1");return 0;} for(i=2;i<=10;i++){ tmp+=k; if(tmp%10==r||tmp%10==0) break; } cout<<i<<endl; } |
732B. Cormen — The Best Friend Of a Man
根据题模拟一下。如果出现少于k次的话,尽量放到第二天了,算是一个贪心?
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 |
#include <bits/stdc++.h> #define REP(i,x,y) for(int i=x;i<(y);i++) using namespace std; int n,k; int a[555]; int main() { scanf("%d %d",&n,&k); REP(i,1,n+1) scanf("%d",&a[i]); if(n==1) { printf("%d\n%d\n",0,a[1]); return 0; } int ans=0; REP(i,2,n){ if(a[i-1]+a[i]<k){ ans+=k-a[i-1]-a[i]; a[i]+=k-a[i-1]-a[i]; } } if(a[n-1]+a[n]<k) { ans+=k-a[n]-a[n-1]; a[n]+=k-a[n]-a[n-1]; } printf("%d\n",ans); REP(i,1,n+1){ if(i!=1) printf(" "); printf("%d",a[i]); } puts(""); } |
732C. Sanatorium
题意:给出b,d,s分别代表吃了多少天的早饭,中饭和晚饭。你可能忘记吃了一些次的饭,现在需要求出最少可能忘记吃了多少次饭。
首先需要确定一个天数,找出吃了最多次数的饭,那么减去1就是最少过了这么多天。然后和剩下的两个比比,就可以求出答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[5]; int main() { scanf("%I64d %I64d %I64d",&a[1],&a[2],&a[3]); sort(a+1,a+4); ll maxx=a[3]-1; ll ans=(maxx>=a[1] ? maxx-a[1] : 0); ans+=(maxx>=a[2] ? maxx-a[2] : 0); printf("%I64d\n",ans); } |
732F. Tourist Reform
题意:给出n个点m条边的一个无向图。保证没有重边。现在对每一条边定向,每个节点都可以有一个值r。代表这个点可以从i到达多少个点。现在需要求出让最少的r值最大的分配方案。
把所有的边双联通分量求出来,那么就形成了一个个连通块,连通块之间有桥边。那么在各个连通块内,我们dfs走出来环就可以给这个连通块内的各个边定向。而且因为是在连通分量内,所以这些边的定向是无所谓的。现在考虑桥边如何定向。其实想一想,把所有连通块缩点后只保留桥边,那么就形成了一个无根树。那么最后剩下来的最小的r一定是在某一个连通块内。这个连通块的桥边都是指向他的没有出边。也就是根节点。那么最大的最少r应该正是最大的连通块中点的个数。其余别的连通块的桥边均指向这个根就可以了。
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 |
#include <bits/stdc++.h> #define maxn 400050 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; typedef pair<int,int> pii; int n,m,dfs_clock; struct edge{ int u,v,flag,id; edge(int _u,int _v,int _f,int i):u(_u),v(_v),flag(_f),id(i){} }; vector<int>e[maxn]; vector<edge>edges; void add_edge(int u,int v,int i){ edges.push_back(edge(u,v,0,i)); edges.push_back(edge(v,u,0,i)); int cnt=edges.size(); e[u].push_back(cnt-2);e[v].push_back(cnt-1); } int pre[maxn],low[maxn]; void dfs_bcc(int u,int fa){ pre[u]=low[u]=(++dfs_clock); int Size=e[u].size(); for(int i=0;i<Size;i++){ int Next=e[u][i]; int v=edges[Next].v; if(v==fa) continue; if(!pre[v]){ dfs_bcc(v,u); low[u]=min(low[u],low[v]); if(low[v]>pre[u]) edges[Next].flag=edges[Next^1].flag=1; } else if(pre[v]<pre[u]) low[u]=min(low[u],pre[v]); } } int vis[maxn],col,cnt[maxn],cnt2[maxn]; pii ans[maxn]; void dfs(int u,int fa,int col){ vis[u]=col;int Size=e[u].size(); for(int i=0;i<Size;i++){ int Next=e[u][i]; int v=edges[Next].v; if(v==fa||edges[Next].flag) continue; ans[edges[Next].id]=make_pair(u,v); edges[Next].flag=edges[Next^1].flag=2; if(vis[v]==col) continue; dfs(v,u,col); } } int vis2[maxn]; void bfs(int st){ queue<int>que; que.push(st);vis2[st]=1; while(!que.empty()){ int now=que.front();que.pop(); int Size=e[now].size(); for(int i=0;i<Size;i++){ int Next=e[now][i]; int v=edges[Next].v; if(vis2[v]) continue; if(edges[Next].flag==1) ans[edges[Next].id]=make_pair(v,now); vis2[v]=1; que.push(v); } } } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=m;i++){ int u,v;scanf("%d %d",&u,&v); add_edge(u,v,i); } dfs_clock=0; dfs_bcc(1,0); for(int i=1;i<=n;i++) if(!vis[i]) col++,dfs(i,0,col); int maxx=0,pos=-1; for(int i=1;i<=n;i++) cnt[vis[i]]++; for(int i=1;i<=n;i++){ if(maxx<cnt[vis[i]]){ maxx=cnt[vis[i]]; pos=i; } } printf("%d\n",maxx); bfs(pos); for(int i=1;i<=m;i++) printf("%d %d\n",ans[i].first,ans[i].second); } |