A题
传送门
题意简述：
一个人要完成一件事总共需要ttt秒，现在有nnn天，每天有aia_iai不能做事，问他可以在第几天做完。
思路：按照题意模拟。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=105;
int n,t,a[N];
int main(){
n=read(),t=read();
for(ri i=1;i<=n;++i){
t-=(86400-read());
if(t<=0)return cout<<i,0;
}
return 0;
}
B题
传送门
题意：给一个长度为xxx的010101串，有nnn段分开的连续的111，长度分别为a1,a2,...,ana_1,a_2,...,a_na1,a2,...,an，现在问你是否只存在一种010101串构造方式满足条件。
思路：按照题意模拟。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=105;
int n,x,a[N];
int main(){
n=read(),x=read();
int sum=-1;
for(ri i=1;i<=n;++i)sum+=read()+1;
puts(sum==x?"YES":"NO");
return 0;
}
C题
传送门
题意：给你nnn个点组成的有向环森林，最多可以对两条边进行操作，使得(u,v)(u,v)(u,v)变成(u,v′)(u,v')(u,v′)，操作之后需要保证还是有向环森林，每个环贡献是环上点个数的平方，问最后得到的贡献最大值。
思路：用并查集搞一下，然后把最大的两个环并起来即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef long long ll;
const int N=1e5+5;
int n,a[N],siz[N],anc[N];
inline int find(const int&x){return x^anc[x]?anc[x]=find(anc[x]):x;}
int main(){
n=read();
for(ri i=1;i<=n;++i)anc[i]=i,siz[i]=1;
for(ri i=1;i<=n;++i){
int fx=find(read()),fy=find(i);
if(fx^fy){
anc[fx]=fy,siz[fy]+=siz[fx];
}
}
vector<int>sum;
for(ri i=1;i<=n;++i){
if(i^anc[i])continue;
sum.push_back(siz[i]);
}
sort(sum.begin(),sum.end());
if(sum.size()==1)return cout<<(ll)sum[0]*sum[0],0;
ll ans=0;
for(ri i=sum.size()-3;~i;--i)ans+=(ll)sum[i]*sum[i];
ans+=(ll)(sum[sum.size()-1]+sum[sum.size()-2])*(sum[sum.size()-1]+sum[sum.size()-2]);
cout<<ans;
return 0;
}
D题
传送门
题意：有nnn种不同颜色的球和nnn个盒子，个数分别为a1,a2,...,ana_1,a_2,...,a_na1,a2,...,an，现在这些球全部被放在第一个盒子里面。
你每次可以从一个盒子里面拿出所有的球，然后分到两个或者三个盒子里面，最后要求第iii种颜色的球全部装在第iii个盒子里面，每次拿球的代价为拿的个数，问总代价最小值。
思路：
考虑逆向思考，就变成了合并果子，显然如果能把3个合并就合并三个，只剩两个就只合并两个。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef long long ll;
const int N=2e5+5;
int n,cnt[N];
ll ans=0,sum[N];
priority_queue<ll,vector<ll>,greater<ll> >q;
int main(){
n=read();
for(ri i=1;i<=n;++i)q.push(read());
if(n==n/2*2)q.push(0);
while(q.size()>1){
ll a=q.top(),b=0,c=0,d;
q.pop();
if(!q.empty())b=q.top(),q.pop();
if(!q.empty())c=q.top(),q.pop();
d=a+b+c;
ans+=d;
q.push(d);
}
cout<<ans;
return 0;
}
E题
传送门
题意：给一个n∗mn*mn∗m的010101矩阵n≤212,m≤214n\le2^{12},m\le2^{14}n≤212,m≤214，问111的连通块数，空间限制16MB16MB16MB。
思路：显然不能开一个二维数组，需要一行一行的模拟，因此可以用并查集合并自己左方和上方的格子。
答案=1=1=1的个数−-−成功合并次数。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1<<14|5;
char s[N];
int n,m,ans=0,f[N<<1],g[N];
inline int trans(const char&x){return isdigit(x)?x^48:x-'A'+10;}
inline int getf(int x){
if(x<0||x>m-1)return 0;
return trans(s[x/4])>>(3-x%4)&1;
}
inline int find(const int&x){return x^f[x]?f[x]=find(f[x]):x;}
inline void merge(int x,int y){
int fx=find(x),fy=find(y);
fx^fy?f[fx]=fy,--ans:0;
}
int main(){
scanf("%d%d",&n,&m);
memset(f,-1,sizeof(f));
for(ri i=0;i<n;++i){
scanf("%s",s);
for(ri j=0;j<m;++j)g[j]=getf(j);
for(ri j=0;j<m;++j)g[j]?++ans,f[j+m]=j+m:f[j+m]=-1;
for(ri j=0;j<m;++j){
if(!g[j])continue;
if(~f[j])merge(j,j+m);
if(getf(j-1))merge(j+m-1,j+m);
}
for(ri j=0;j<m;++j)f[j]=g[j]?find(j+m)-m:-1;
}
cout<<ans;
return 0;
}
F题
传送门
题意：对于一个长度为偶数的字符串SSS，如果满足Si≠Sn−i+1S_i =\not S_{n-i+1}Si≠Sn−i+1那么称其为反回文串。
现在要将一个字符串SSS重新排列成一个反回文串TTT，每个位置对应一个权值aia_iai，TTT的价值等于∑Si==Tiai\sum\limits_{S_i==T_i}a_iSi==Ti∑ai，求得到的价值最大值。
思路：
考虑上费用流。
把所有的字母和位置拿出来建图匹配即可。
这篇博客写的很不错
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=50005,M=200005;
char s[N];
int n,m,ans=0,a[N],b[N],cnt[N];
namespace mcmf{
int d[N],flow[N],pos[N],pred[N],s,t,first[N],cnt,F=0;
bool in[N];
struct edge{int v,next,c,w;}e[M];
inline void init(){memset(first,-1,sizeof(first)),cnt=-1,s=0,t=n+26+n*13+1;}
inline void addedge(const int&u,const int&v,const int&c,const int&w){e[++cnt]=(edge){v,first[u],c,w},first[u]=cnt;}
inline void add(const int&u,const int&v,const int&c,const int&w){addedge(u,v,c,w),addedge(v,u,0,-w);}
inline bool bfs(){
static int q[N],hd,tl;
for(ri i=s;i<=t;++i)d[i]=-0x3f3f3f3f,flow[i]=0x3f3f3f3f;
d[q[hd=tl=1]=s]=0,in[s]=1;
while(hd<=tl){
int x=q[hd++];
in[x]=0;
for(ri i=first[x],v;~i;i=e[i].next){
if(e[i].c&&d[x]+e[i].w>d[v=e[i].v]){
d[v]=d[x]+e[i].w,pred[v]=x,pos[v]=i,flow[v]=min(flow[x],e[i].c);
if(!in[v])q[++tl]=v,in[v]=1;
}
}
}
if(d[t]==-0x3f3f3f3f)return 0;
int p=t;
F+=flow[t]*d[t];
while(p^s)e[pos[p]].c-=flow[t],e[pos[p]^1].c+=flow[t],p=pred[p];
return 1;
}
}
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline int idx(int a,int b){return n+26+a*n/2+b;}
int main(){
n=read(),scanf("%s",s+1);
mcmf::init();
for(ri i=1;i<=n;++i)++cnt[a[i]=s[i]-'a'],b[i]=read(),mcmf::add(i,mcmf::t,1,0);
for(ri i=0;i<26;++i)mcmf::add(mcmf::s,i+1+n,cnt[i],0);
for(ri i=0;i<26;++i){
for(ri j=1;j<=n/2;++j){
mcmf::add(i+1+n,idx(i,j),1,0);
mcmf::add(idx(i,j),j,1,a[j]==i?b[j]:0);
mcmf::add(idx(i,j),n-j+1,1,a[n-j+1]==i?b[n-j+1]:0);
}
}
while(mcmf::bfs());
cout<<mcmf::F;
return 0;
}