A.Creating a Character
题意
有 $T$ 组测试数据，每组测试数据有 $str, int, exp$ 三个参数，可将 $str, int$ 增加， 增加的总和严格等于 $exp$ ， 求有多少种方案使得增加后 $str > int$ 。
$T\le 100 \ , \ str,int,exp\le 10^8$ 。
题解
可以算出增加后 $str$ 的最小值，然后给 $str$ 分配后答案即为剩余的 $exp+1$ 。注意如果 $str$ 已经满足答案就是 $exp+1$ 。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int t,a,b,c;
signed main()
{
t=read();
while (t--)
{
a=read(); b=read(); c=read();
int mina=((a+b+c)>>1)+1;
if (mina>=a) printf("%d\n",max(0,c-mina+a+1));
else printf("%d\n",c+1);
}
return 0;
}B.Zmei Gorynich
题意
$T$ 组测试数据。一条恶龙有 $x$ 个头， 你有 $n$ 个技能，每个技能无限使用：每次砍掉 $d_i$ 个头，长出 $h_i$ 个头，（砍掉后头数小于等于 $0$ 时不再生长）。 问：最少使用多少次技能可以杀死恶龙，如果无法杀死，输出 -1 。
题解
显然应该先一直砍 $d_i-h_i$ 最大的，直到剩下的头数 $\le d_{max}$ 再一次性全部砍掉。
特殊情况需要提前考虑。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int t,n,x,d[105],h[105];
signed main()
{
t=read();
while (t--)
{
n=read(); x=read();
int maxD=0,maxDelta=0;
for (int i=1;i<=n;i++)
{
d[i]=read(); h[i]=read();
maxD=max(maxD,d[i]);
maxDelta=max(maxDelta,d[i]-h[i]);
}
if (x<=maxD) { puts("1"); continue; } //直接取完
if (maxDelta<=0) { puts("-1"); continue; } //无解
int ans=(x-maxD+maxDelta-1)/maxDelta;
printf("%d\n",ans+1);
}
return 0;
}C.The Number Of Good Substrings
题意
令 $f(x_2)=x_{10}$ ，$x_2$ 为 $x$ 的二进制，可以有前导 $0$ 。问一个二进制串中有多少个子串 $x$ 满足 $f(x)=len_x$ 。
二进制串长度 $\le 200000$ 。
题解
$2^{18}=262144$ ，所以一个以 $1$ 开头的子串最多 $18$ 位。
我最开始就直接从每一位开始枚举 $20$ 位，然后就 $WA$ 了。后来才发现有可能有多个前导 $0$ ，所以可以预处理出 $i$ 右边的第一个 $1$ 的位置 $nxt[i]$（可以是 $i$），然后从 $nxt[i]$ 开始枚举 $20$ 位即可。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=200005;
int t,n,nxt[N];
char s[N];
signed main()
{
t=read();
while (t--)
{
int ans=0;
scanf("%s",s+1);
n=strlen(s+1);
nxt[n+1]=n+1;
for (int i=n;i;i--)
{
nxt[i]=nxt[i+1];
if (s[i]=='1') nxt[i]=i;
}
for (int i=1;i<=n;i++)
{
int cur=0,maxj=min(n,nxt[i]+19);
for (int j=nxt[i];j<=maxj;j++)
{
cur=cur<<1|(s[j]-'0');
if (cur==j-i+1) ans++;
}
}
printf("%d\n",ans);
}
return 0;
}D. Coloring Edges
题意
请给一个 $N$ 点 $M$ 边的有向图着色，使得没有一个环只有一个颜色，您需要最小化使用颜色的数量。
$N,M\le 5000$ 。
题解
可以发现如果没有环就只用 $1$ 种颜色，否则 $2$ 种。
然后对于输入的每一条边 $a\rightarrow b$ ，都以 $b$ 为起点搜索，如果 $a$ 被访问过就说明成环了，就把 $a\rightarrow b$ 染色；否则连边 $a\rightarrow b$ 。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=5005;
struct Edge {
int next,to;
} edge[N];
bool vis[N],col[N];
int cnt,head[N],n,m,a,b,ans;
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int x)
{
vis[x]=1;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (vis[y]) continue;
dfs(y);
}
}
signed main()
{
n=read(); m=read();
for (int i=1;i<=m;i++)
{
a=read(); b=read();
memset(vis,0,sizeof(vis));
dfs(b);
if (vis[a]) ans=col[i]=1;
else add(a,b);
}
printf("%d\n",ans+1);
for (int i=1;i<=m;i++) printf("%d ",col[i]+1);
return 0;
}