i207M的“怕不是一个小时就要弃疗的flag”并没有生效，这次居然写到了最后，好评=。=
然而可能是退役前和i207M的最后一场比赛了TAT
不过打得真的好爽啊QAQ
最终结果：
看见那几个罚时没，全是我贡献的，还全是睿智的细节错误(逃
不罚时估计就进前100了啊QAQ，我好菜啊.jpg
我切了3道(然后挂了四次2333，i207M切了4道(orz)，具体比赛历程太长了，不好写，就在题上写吧=。=
A.Find a Number
开场不到十分钟就有神仙切了这神仙题
因为种种原因，这题到吃晚饭的时候才开。i207M想一个很好写的$dp$思路，然而我觉得状态量太大做不了，不过后来他证明了如果有解答案不超过max(d,s/9)位(咕咕原理，如果有解在模$d$剩余系下每$d$位一定会循环)，然后我们并没有想出怎么构造最优解=。=
到九点多ztb神仙成功切掉了，然后知道了构造最优解就是从高位向低位贪心，用DFS实现即可，于是i207M一发A掉了orz
至于那个简单的$dp$就是设$dp[i][j][k]$表示$i$位时模$d$为$j$数位和为$k$是否可行，然后用bitset优化空间，用循环移位实现转移
↓我赛后补的代码
#include<cstdio>
#include<bitset>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=,S=;
bitset<M> bit[N][S];
int pw[N],d,s;
void outp(int pos,int sum,int mod)
{
if(!pos) return;
for(int i=;i<=;i++)
{
int newm=((mod-i*pw[pos-]%d)%d+d)%d;
if(bit[pos-][sum-i][newm])
{
printf("%d",i);
outp(pos-,sum-i,newm);
return;
}
}
}
int main()
{
bit[][][]=true;
scanf("%d%d",&d,&s),pw[]=;
for(int i=;i<N;i++) pw[i]=pw[i-]*%d;
for(int i=;i<N;i++)
{
int sum=min(*i,s);
for(int j=;j<=sum;j++)
for(int k=;k<=min(,j);k++)
{
int mov=pw[i-]*k%d;
bitset<M> las=bit[i-][j-k];
bit[i][j]|=(las<<mov)|(las>>(d-mov));
}
if(bit[i][s][]) outp(i,s,),exit();
}
printf("-1");
return ;
}
B. Berkomnadzor
题面都是纸老虎！
i207M最后时刻搞出正解没时间写完了orz
将每个串按照题意转化为01序列后构建一棵01Trie，然后对于一个黑名单地址其子树都必须不可行，对于一个白名单地址从根节点到它的链都必须可行。因为树高只有32我们每个串暴力向上跳检查即可，注意判断无解时的细节(i207M和ZRQ都被阴了，论WA on test 217是什么体验=。=
这是i207M赛后的代码我咕掉了
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<sstream>
using namespace std;
#define ri register int
#define LL long long
#define il inline
#define mp make_pair
#define pb push_back
#define pairint pair<int,int>
#define fi first
#define se second
#define gc getchar
template<class T>il void in(T &x)
{
x=; bool f=; char c=gc();
while(c<''||c>'')
{
if(c=='-') f=;
c=gc();
}
while(c>=''&&c<='') x=x*+(c^''),c=gc();
if(f) x=-x;
}
#undef gc
#define int LL
int tre[*][],cnt=;
int fa[*];
int n;
char tc[];
const int rt=;
bool del[*],hv[*],phv[*];
int d[],cntd,h[],cnth;
void inser(int num,int mx,int typ)
{
int x=rt;
if(mx==)
{
if(typ) del[x]=,d[++cntd]=x;
else hv[x]=,h[++cnth]=x,phv[x]=;
return;
}
for(ri i=; i>=; --i)
{
if(!tre[x][(num>>i)&]) tre[x][(num>>i)&]=++cnt,fa[cnt]=x;
x=tre[x][(num>>i)&];
// printf("I %lld\n",x);
if(-i==mx)
{
if(typ) del[x]=,d[++cntd]=x;
else hv[x]=,h[++cnth]=x,phv[x]=;
break;
}
}
}
void ins()
{
int len=strlen(tc+),wei=,p=,num=,mx=;
for(; wei<;)
{
int x=;
while(p<=len&&isdigit(tc[p])) x=x*+tc[p]-'',++p;
if(wei==) num+=x<<;
else if(wei==) num+=x<<;
else if(wei==) num+=x<<;
else num+=x;
// printf("X %lld\n",x);
++wei; ++p;
}
if(p<=len)
{
// cout<<"A";
int x=;
while(p<=len&&isdigit(tc[p])) x=x*+tc[p]-'',++p;
mx=x;
}
// cout<<bitset<32>(num);
// printf("S %lld %lld\n",mx,(int)(tc[1]=='-'));
inser(num,mx,tc[]=='-');
}
void gun()
{
puts("-1");
exit();
}
vector<string>ans;
const int bit=(<<)-;
void toans(int num,int mx)
{
num<<=-mx;
// cout<<bitset<32>(num)<<"D"<<endl;
stringstream str;
for(ri wei=; wei<; ++wei)
{
int x=(num&(bit<<((-wei-)*)))>>((-wei-)*);
str<<x;
if(wei<) str<<".";
else str<<"/";
}
str<<mx;
string res;
str>>res;
ans.pb(res);
}
void dfs(int x,int num,int dep)
{
if(!x) return;
// cout<<bitset<32>(num);
// printf(" %lld %lld\n",(int)hv[x],(int)del[x]);
if(del[x])
{
// cout<<"BBBBBBBB";
toans(num,dep);
return;
}
dfs(tre[x][],num<<,dep+);
// cout<<"A";
dfs(tre[x][],num<<|,dep+);
}
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
#endif
in(n);
for(ri i=; i<=n; ++i)
{
scanf("%s",tc+);
ins();
}
sort(d+,d++cntd);
cntd=unique(d+,d++cntd)-d-;
sort(h+,h++cnth);
cnth=unique(h+,h++cnth)-h-;
for(ri i=; i<=cnth; ++i)
{
int x=h[i];
while(x)
{
if(del[x]) gun();
hv[x]=;
x=fa[x];
// if(hv[x]) break;
}
}
for(ri i=; i<=cntd; ++i)
{
int x=d[i];
while(x)
{
if(phv[x]) gun();
if(hv[x]) break;
del[x]=;
x=fa[x];
}
}
dfs(,,);
printf("%lld\n",(int)ans.size());
for(ri i=; i<(int)ans.size(); ++i) cout<<ans[i]<<'\n';
return ;
}
C.Cloud Computing
建立一棵权值线段树，将区间依次加入/删除，每次二分出最优解即可
这题也是i207M的，比赛的时候这题被切出来之后咕了好长时间才写完233(别着急我的水题在后面)
↓我补的代码
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=1e6+;
struct a{long long cnt,pri;};
vector<a> lv[M],rv[M];
long long n,k,m,len,ans;
long long num[*N],val[*N];
long long ll[N],rr[N],cc[N],pp[N],uni[N];
void add(int nde,int l,int r,int pos,int task)
{
if(l==r)
num[nde]+=task,val[nde]=num[nde]*uni[l];
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+;
(pos<=mid)?add(ls,l,mid,pos,task):add(rs,mid+,r,pos,task);
num[nde]=num[ls]+num[rs],val[nde]=val[ls]+val[rs];
}
}
long long query(int nde,int l,int r,long long task)
{
if(!num[nde]) return ;
if(l==r) return min(task,num[nde])*uni[l];
int mid=(l+r)/,ls=*nde,rs=*nde+;
if(num[ls]>=task) return query(ls,l,mid,task);
else return val[ls]+query(rs,mid+,r,task-num[ls]);
}
int main()
{
scanf("%lld%lld%lld",&n,&k,&m);
for(int i=;i<=m;i++)
scanf("%lld%lld%lld%lld",&ll[i],&rr[i],&cc[i],&pp[i]),uni[i]=pp[i];
sort(uni+,uni++m); len=unique(uni+,uni++m)-uni-;
for(int i=;i<=m;i++)
{
pp[i]=lower_bound(uni+,uni++len,pp[i])-uni;
lv[ll[i]].push_back((a){cc[i],pp[i]});
rv[rr[i]].push_back((a){cc[i],pp[i]});
}
for(int i=;i<=n;i++)
{
for(int j=;j<(int)lv[i].size();j++)
add(,,len,lv[i][j].pri,lv[i][j].cnt);
ans+=query(,,len,k);
for(int j=;j<(int)rv[i].size();j++)
add(,,len,rv[i][j].pri,-rv[i][j].cnt);
}
printf("%lld",ans);
return ;
}
D.Garbage Disposal
按题意模拟，每天看看昨天剩下的，然后再看看今天的，最后搞不掉的剩到明天=。=(我保证马上就是我的题了QAQ
这题没补......
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<stack>
using namespace std;
#define ri register int
#define LL long long
#define il inline
#define mp make_pair
#define pb push_back
#define pairint pair<int,int>
#define fi first
#define se second
#define gc getchar
template<class T>il void in(T &x)
{
x=; bool f=; char c=gc();
while(c<''||c>'')
{
if(c=='-') f=;
c=gc();
}
while(c>=''&&c<='') x=x*+(c^''),c=gc();
if(f) x=-x;
}
#undef gc
#define N 200005
#define int LL
int a[N];
int b[N];
int n,k;
int ans;
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
#endif
in(n); in(k);
for(ri i=; i<=n; ++i)
{
in(a[i]);
int t=(a[i]+b[i])/k;
// printf("U %lld %lld\n",a[i],b[i]);
if(t*k>=b[i])
{
ans+=t;
t*=k;
t-=b[i];
b[i]=;
// printf("T %lld %lld %lld\n",i,t,a[i]);
a[i]-=t;
b[i+]+=a[i];
}
else
{
t=(b[i]+k-)/k;
ans+=t;
// printf("Q %lld %lld\n",i,t);
t*=k;
t-=b[i];
a[i]-=t;
a[i]=max(a[i],0ll);
b[i+]+=a[i];
}
}
ans+=(b[n+]+k-)/k;
printf("%lld",ans);
return ;
}
E.Getting Deals Done
终于到了蒟蒻的水题辣
发现这个阈值好像并不好二分(也许是可以的？)，但是又发现完成的数量越多阈值肯定是越小，因为这题里难度=完成时间，这是有单调性的，可以二分！
二分后如何检查？我们先不考虑时间限制，只是考虑做完这些任务，发现将任务排序后第$mid$个就是我们要的阈值！那么就按题意模拟然后看看是否超时即可，注意做够$mid$个任务我们就不用做了，还有d是正整数=。=......还有就是注意细节啊
所以你就把数组开小又没开long long贡献了一个WA+一个RE？
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
long long a[N],b[N];
long long T,n,m,t,l,r,ans;
bool check(long long x,long long md)
{
long long tm=,noww=,cnt=,tot=;
for(int i=;i<=n;i++)
if(b[i]<=x)
{
tot++,cnt++,tm+=b[i],noww+=b[i];
if(tot>=md) return tm<=t;
if(cnt==m) cnt=,tm+=noww,noww=;
}
return tm<=t;
}
int main ()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld%lld",&n,&m,&t),a[]=;
for(int i=;i<=n;i++)
scanf("%lld",&b[i]),a[i]=b[i];
sort(a+,a++n),l=,r=n;
while(l<=r)
{
int mid=(l+r)/,td=a[mid];
if(check(td,mid)) ans=mid,l=mid+;
else r=mid-;
}
printf("%lld %lld\n",ans,a[ans]);
}
return ;
}
F.Debate
个人比较喜欢的贪心题，就把这个题切掉辣
首先先把两个人都支持的全选了，这样答案只会越来越合法；然后我们从只支持一个人的两堆人里的前$siz$大的人都选了，其中$siz$是两堆人中较小的那堆人的数量，这样答案一定还是合法的；最后把剩下的丢进大根堆选到不能选为止......
注意像我这样最后把多选的那个不合法的人丢掉的话要判断是不是选完了都是合法的你就不能换个不这么毒瘤的写法吗，又贡献了一个WA=。=
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
long long typ[],ali[N],bob[N],non[N],all[N];
struct a
{
long long v,t;
};
bool operator < (a x,a y)
{
return x.v<y.v;
}
priority_queue<a> hp1; char ss[];
long long n,rd,c1,c2,c3,c4,cc1,cc2,peo,ans,b1,b2,mem;
int gkind(char *s)
{
if(s[]==s[]&&s[]=='') return ;
if(s[]==s[]&&s[]=='') return ;
if(s[]=='') return ;
else return ;
}
bool cmp(long long a,long long b)
{
return a>b;
}
int main ()
{
scanf("%lld",&n);
for(int i=;i<=n;i++)
{
scanf("%s%lld",ss,&rd);
b1|=(ss[]-''),b2|=(ss[]-'');
int tmp=gkind(ss); typ[tmp]++;
if(tmp==) ali[++c1]=rd;
else if(tmp==) bob[++c2]=rd;
else if(tmp==) ans+=rd,cc1++,cc2++,peo++;
else non[++c4]=rd;
}
if(!b1||!b2) printf(""),exit();
int siz=min(c1,c2);
sort(ali+,ali++c1,cmp);
sort(bob+,bob++c2,cmp);
for(int i=;i<=siz;i++)
ans+=ali[i]+bob[i],cc1++,cc2++,peo+=;
if(siz==c1)
for(int i=siz+;i<=c2;i++) hp1.push((a){bob[i],});
else
for(int i=siz+;i<=c1;i++) hp1.push((a){ali[i],});
for(int i=;i<=c4;i++) hp1.push((a){non[i],});
while(!hp1.empty()&&cc1>=(peo+)/&&cc2>=(peo+)/)
{
a tp=hp1.top(); hp1.pop();
ans+=tp.v,mem=tp.v;
if(tp.t==) cc1++,peo++;
else if(tp.t==) cc2++,peo++;
else peo++;
}
if(cc1<(peo+)/||cc2<(peo+)/) ans-=mem;
printf("%lld",ans);
return ;
}
G.Monsters and Potions
比赛的时候我俩都觉得这题讨论太多了然后就弃掉了，其实下来分析完是个模拟题2333
枚举位置从两边向中间按题意模拟，贪心让血量最高的英雄来打怪/吃药
↓补的代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,inf=2e9;
int n,m,rd,flag,mini,maxx;
int num[N],hel[N],val[N],outp[N],mark[N];
bool able(int pos)
{
int noww=,pts=,ok=;
for(int i=maxx;i>pos;i--)
{
if(noww<hel[num[i]])
outp[++pts]=num[i],noww=hel[num[i]];
noww+=val[i]; if(noww<) return false;
}
ok|=(noww+val[pos]>=),noww=;
for(int i=mini;i<pos;i++)
{
if(noww<hel[num[i]])
outp[++pts]=num[i],noww=hel[num[i]];
noww+=val[i]; if(noww<) return false;
}
ok|=(noww+val[pos]>=);
if(!ok) return false; printf("%d\n",pos);
while(pts)
printf("%d ",outp[pts]),mark[outp[pts--]]=true;
for(int i=;i<=m;i++) if(!mark[i]) printf("%d ",i);
return true;
}
int main ()
{
scanf("%d%d",&n,&m);
hel[]=-inf,mini=inf,maxx=-inf;
for(int i=;i<=m;i++)
{
scanf("%d%d",&rd,&hel[i]),num[rd]=i;
mini=min(mini,rd),maxx=max(maxx,rd);
}
for(int i=;i<=n;i++)
scanf("%d",&val[i]);
for(int i=;i<=n;i++)
if(able(i)) return ;
printf("-1");
return ;
}
H.BerOS File Suggestion
我一开始以为是AC自动机，然后因为我不会AC自动机就给i207M了。结果最后发现串长太小了，在Trie上打标记，对每个串暴力跑就行了......
这题也咕了......
update on 2018.10.23:
昨天才说咕掉算了，结果今天考试就考了个弱化版，那就把考试的代码随便改改放上来算了=。=
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
char rd[],str[N*][];
int n,m,tot,len,nde,ans,flag;
int cnt[N*],mark[N*],trie[N*][];
int turn(char ch)
{
if(isdigit(ch)) return ch-'';
else if(ch>='a'&&ch<='z')
return ch-'a'+;
else return ;
}
int main()
{
register int i,j,k,h;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%s",rd+);
len=strlen(rd+);
for(j=len;j;j--)
{
nde=;
for(k=j;k<=len;k++)
{
int ch=turn(rd[k]);
if(!trie[nde][ch])
trie[nde][ch]=++tot;
nde=trie[nde][ch];
if(mark[nde]!=i)
{
cnt[nde]++,mark[nde]=i;
memset(str[nde],,sizeof str[nde]);
for(h=;h<=len;h++) str[nde][h]=rd[h];
}
}
}
}
scanf("%d",&m);
for(i=;i<=m;i++)
{
scanf("%s",rd+);
len=strlen(rd+),flag=true,nde=;
for(j=;j<=len;j++)
{
int ch=turn(rd[j]);
if(!trie[nde][ch])
{flag=; break;}
nde=trie[nde][ch];
}
flag?printf("%d %s\n",cnt[nde],str[nde]+):printf("0 -\n");
}
return ;
}
I.Privatization of Roads in Berland
i207M太强了，比赛的时候居然看出来了是个网络流
这题咕了没啥可说的吧=。=
J.Streets and Avenues in Berhattan
我在最后时刻分析出了性质，结果走偏了，不知道怎么开始暴力讨论去了TAT
这个性质就是我们一定可以构造一个最优解使得重复的都是一种字母，否则这个解不可能优于最优解(建议自己写写画画
于是我们枚举哪种字母是最后重复的，对剩下的做01背包得出可行的重复长度，枚举一边的长度更新答案即可
注意在保证输入总量而不是数据组数的时候不要memset，手动赋值才是对的
↓这是我赛后补的代码
#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int T,n,m,k,len,ans;
int cnt[],dp[N];
char rd[N];
bool cmp(int a,int b)
{
return a>b;
}
void init()
{
len=strlen(rd+),ans=n*m;
memset(cnt,,sizeof cnt);
for(int i=;i<=len;i++)
cnt[rd[i]-'A'+]++;
}
int main ()
{
register int i,j,h;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
scanf("%s",rd+),init();
for(i=;i<=;i++)
{
for(j=;j<=k;j++) dp[j]=; dp[]=;
for(j=;j<=;j++)
if(j!=i)
for(h=k;h>=cnt[j];h--)
dp[h]|=dp[h-cnt[j]];
for(j=;j<=k;j++)
if(dp[j])
{
int xx=max(,n-j),yy=max(,m-(k-cnt[i]-j));
if(xx+yy<=cnt[i]) ans=min(ans,xx*yy);
}
}
printf("%d\n",ans);
}
return ;
}
K.Video Posts
本来是个模拟水题，结果我少判了一种无解(有个特别大的数不能拆)，贡献了一个制杖的罚时TAT
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
long long n,k,sum,goal,noww,last;
long long a[N],b[N],cnt;
int main ()
{
scanf("%lld%lld",&n,&k);
for(int i=;i<=n;i++)
scanf("%lld",&a[i]),sum+=a[i];
if(sum%k) printf("No"),exit();
goal=sum/k;
for(int i=;i<=n;i++)
{
noww+=a[i];
if(noww==goal)
b[++cnt]=i-last,noww=,last=i;
}
if(cnt!=k) printf("No"),exit();
printf("Yes\n");
for(int i=;i<=k;i++)
printf("%lld ",b[i]);
return ;
}
L.Odd Federalization
大力讨论题，做不来，gal辞(雾
M.Algoland and Berland
全场只有一个AC的神仙题，摸了......
希望还能再和i207M一起打更多的比赛，可是我真的马上要退役了TAT