Educational Codeforces Round 72 (Rated for Div. 2)
Creating a Character
游戏中有位英雄，有 a 点体力，b 点智力，c 点未分配属性，你要将 c 全部分出去但是保证 a>b 求有多少种分法
int main()
{IOS;rush(){ll a,b,c;cin>>a>>b>>c;a+=c;//先全给体力ll ans=min(c,a-1-b>>1 );if(a>b) ans++;if(ans<0) ans=0;cout<<ans<<endl;}// PAUSE;
}
Zmei Gorynich（贪心）
游戏中有个怪兽有 x 个头，你有 n 把弓箭，每把弓箭会先射杀怪兽的 a 个头，然后怪兽会再补给 b 个头，问最少需要射几次
每把弓箭可重复使用
int main()
{IOS;rush(){ll cur,d,h;cin>>n>>cur;Pair in;//消耗ll maxx=0,res=0; //maxx 最后一击for(i=1;i<=n;i++){cin>>d>>h;if(res<d-h) res=d-h,in=Pair{d,h};maxx=max(maxx,d);}d=in.fr,h=in.sc;//debug(maxx);//debug(res);if(maxx>=cur) cout<<1<<endl;else if(res<=0) cout<<-1<<endl;else{ll ans=(cur-maxx+res-1)/res+1;cout<<ans<<endl;}}//PAUSE;
}
The Number Of Good Substrings (暴力)
给出一个长度为 n 的字符串 s ，包含前导 0，若其字串二进制的数值大小为其长度，那么是一个好的子串，求好子串的个数
对于一个字符串来说，某个数二进制的位数 >= 对应十进制的位数
二进制的前导零决定了好字符串的个数，
统计：前导零 + 当前字符串的长度 = 字符串数值 的个数
特殊的：前导零 + 当前字符串的长度 > 字符串数值 时，可以去掉前导零的个数，
但是要注意前导零的个数因为字符串的长度是逐一递减的，所以只要长度够，总有可能键成当前字符串的数值
考虑到 >2e5 ，所以暴力即可， O(len*20)
int main()
{IOS;rush(){string s;cin>>s;int len=s.size();int pre=0;int ans=0;for(i=0;i<len;i++){if(s[i]=='0') pre++;else{int l=i;int r=i;int binary=1;for(j=0;j<=20;j++){//包含前导零和不包含前导零与当前字符串数值的关系if(binary<=pre+r-l+1 && r-l+1<=binary) ans++;//if(binary<=pre+r-l+1) ans++; //改成这样会更快一点if(r+1>=len) break;binary=(binary<<1)+(s[++r]-'0');//二进制对应的十进制}pre=0;}}cout<<ans<<endl;}//PAUSE;
}
Coloring Edges （判断有向环）
给出一个有 n 个点，m 条边的有向图，每条边从 u->v ， 相同颜色不能形成一个环，求这个图中最多几种颜色
首先要明白只能存在 2 种可能
- 图中无环，一种颜色
- 图中有环，两种颜色，且只有是环的那一部分包含两种颜色
const int N=5000+5;int n,m,t;int i,j,k;vector<int> G[N];int vis[N],flag;int u[N],v[N];void DFS(int u)
{if(!flag) return ;vis[u]=1;int len=G[u].size();for(int i=0;i<len;i++){int v=G[u][i];if(vis[v]==1){ flag=0; return ; }else if(vis[v]==0) DFS(v);}vis[u]=2;
}
int main()
{//IOS;while(sdd(n,m)==2){for(i=1;i<=m;i++){sdd(u[i],v[i]);G[u[i]].pb(v[i]);}ms(vis,0);flag=1;for(i=1;i<=n;i++){if(!vis[i]) DFS(i);}if(flag){pd(1);for(i=1;i<=m;i++) printf("1 ");}else{pd(2);for(i=1;i<=m;i++){if(u[i]<v[i]) printf("1 ");else printf("2 ");}}puts("");}//PAUSE;
}