这场挺难orz
A
tag 有二分emm，但我没二分
把严格大于转化为大于等于，然后求个临界点，特判一下边界即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T; cin>>T;
while(T--){
int a, b, c; cin>>a>>b>>c;
b++;
int t=max((b+c-a+1)/2, 0);
if(t>c) puts("0");
else cout<<c-t+1<<endl;
}
return 0;
}
B
很像小学奥数题蜗牛从井底向上爬
考察在所有技能中：最高伤害的能打多少血、净伤害最高能打多少血。
然后最优策略就是如果前者无法直接打死怪物，就用后者磨怪物的血，最后一刀用前者干掉怪物。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=105;
struct node{
int x, y;
}e[N];
int main(){
int T; read(T);
while(T--){
int n, h; read(n), read(h);
int mx=0, tmp=0;
rep(i,1,n){
int x, y; read(x), read(y);
e[i]={x, y};
mx=max(mx, x), tmp=max(tmp, x-y);
}
if(tmp<=0 && mx<h){
puts("-1");
continue;
}
// debug(tmp);
// debug(ceil(h-mx, tmp));
if(tmp==0) puts("1");
else cout<<max(ceil(h-mx, tmp)+1, 1)<<endl;
}
return 0;
}
C
注意到二进制数不能太大，因为整个串长度本来就不超过 (2e5) ，所以我们暴力模拟并统计即可。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
int main(){
int T; read(T);
while(T--){
int cnt=0;
string s; cin>>s; int n=s.size();
s=' '+s+'#';
int res=0;
rep(i,1,n){
cnt=0;
while(s[i]=='0') cnt++, i++;
if(i>n) break;
int p=i;
res++;
int t=1, len=1;
rep(j,p+1,p+25){
if(j>n) break;
len++;
if(s[j]=='0'){
t<<=1;
if(t<=len+cnt) res++;
}
else{
t=t<<1|1;
if(t<=len+cnt) res++;
}
}
}
cout<<res<<endl;
}
return 0;
}
D
思路很神奇的一道题qwq，如果有向图无环，答案必然是 (1) ，否则答案至少为 (2) ，那么 (2) 种颜色足够合法地染完全部边了吗？答案是肯定的，构造策略：如果边的方向是编号大的向编号小的点就染成 (1) 色，否则染成 (2) 色，显然，对于一个环，必然同时存在编号大的向编号小以及编号小向着编号大的情况。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=5050;
int n, m;
struct hode{
int to, next;
}e[N];
int h[N], tot;
int din[N];
void add(int u, int v){
e[tot].to=v, e[tot].next=h[u], h[u]=tot++;
din[v]++;
}
PII tmp[N];
bool top_sort(){
int q[N]={0};
int tt=-1, hh=0;
int cnt=0;
rep(i,1,n) if(!din[i]) q[++tt]=i, cnt++;
while(tt>=hh){
int hd=q[hh++];
for(int i=h[hd]; ~i; i=e[i].next){
int go=e[i].to;
if(--din[go]==0) q[++tt]=go, cnt++;
}
}
return cnt==n;
}
int main(){
memset(h, -1, sizeof h);
read(n), read(m);
rep(i,1,m){
int u, v; read(u), read(v); tmp[i]={u, v};
add(u, v);
}
if(top_sort()){
puts("1");
rep(i,1,m) cout<<1<<' ';
return 0;
}
puts("2");
rep(i,1,m) cout<<(tmp[i].first>tmp[i].second? 1: 2)<<' ';
cout<<endl;
return 0;
}