比赛的时候E调了好久...F没时间写T T
A：直接走到短的路上来回走就好了
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=,inf=1e9;
int n,a,b,c;
inline void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
int main()
{
read(n);read(a);read(b);read(c);
if(n==)return puts(""),;
int mn=min(a,min(b,c));int now=;
if(a==mn||b==mn)printf("%d\n",mn*(n-));
else printf("%d\n",min(a,b)+mn*(n-));
}
B：将所有数%m，找到最多的相同的数即可
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=,inf=1e9;
int n,k,m,ans,ansi,cntt;
int x[maxn],y[maxn];
int v[maxn];
inline void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
int main()
{
read(n);read(k);read(m);
for(int i=;i<=n;i++)read(x[i]),y[i]=x[i]%m;
for(int i=;i<=n;i++)
{
v[y[i]]++;
if(v[y[i]]>ans)
{
ans=v[y[i]];
ansi=y[i];
}
}
if(ans>=k)
{
puts("Yes");
for(int i=;i<=n;i++)
{
if(y[i]==ansi)printf("%d ",x[i]),cntt++;
if(cntt==k)return ;
}
}
else puts("No");
}
C：答案只可能在[n-100,n]之间，枚举一下就好
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=,inf=1e9;
int n,cnt;
int ans[maxn];
inline void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
int main()
{
read(n);
for(int i=max(,n-);i<=n;i++)
{
int x=i,sum=i;
while(x)
{
sum+=x%;
x/=;
}
if(sum==n)ans[++cnt]=i;
}
printf("%d\n",cnt);
for(int i=;i<=cnt;i++)printf("%d ",ans[i]);
}
D：最后连续的硬币删掉，前面还剩多少个硬币就是答案
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=,inf=1e9;
int n,x;
bool b[maxn];
inline void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
int main()
{
puts("");read(n);int N=n;
for(int i=;i<=n;i++)
{
// printf("%dQAQ\n",N);
read(x);b[x]=;
while(b[N])N--;
printf("%d ",i-(n-N)+);
}
}
E：从每种数字可以改或者不改想到2-SAT，如果第i个字符串比第i+1个字符串小，v[i][j]和v[i+1][j]不一样，那么v[i+1][j]改，v[i][j]就必须改，v[i][j]不改，v[i+1][j]就不能改，如果第i个字符串比第i+1个字符串大，那么v[i][j]必须改，v[i+1][j]不能改，如上连边跑一个可行方案即可。
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=,inf=1e9;
struct poi{int too,pre,x;}e[maxn<<],e2[maxn<<];
int last[maxn],last2[maxn],dfn[maxn],low[maxn],col[maxn],lack[maxn],ru[maxn],rs[maxn],st[maxn],op[maxn];
int n,m,x,y,z,tot,tot2,tott,top,color,flag,len,cnt;
int ans[maxn];
vector<int>v[maxn];
void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
void add(int x,int y){e[++tot].too=y;e[tot].x=x;e[tot].pre=last[x];last[x]=tot;}
void add2(int x,int y){e2[++tot2].too=y;e2[tot2].x=x;e2[tot2].pre=last2[x];last2[x]=tot2;}
int next(int x){return x&?x+:x-;}
void tarjan(int x)
{
dfn[x]=low[x]=++tott;st[++top]=x;lack[x]=top;
for(int i=last[x];i;i=e[i].pre)
if(!dfn[e[i].too])tarjan(e[i].too),low[x]=min(low[x],low[e[i].too]);
else if(!col[e[i].too])low[x]=min(low[x],dfn[e[i].too]);
if(dfn[x]==low[x])for(color++;top>=lack[x];top--)col[st[top]]=color;
}
void topsort()
{
top=;for(int i=;i<=color;i++)if(!ru[i])st[++top]=i;
while(top)
{
int now=st[top--];
if(!rs[now])rs[now]=,rs[op[now]]=;
for(int i=last2[now];i;i=e2[i].pre)
if(!(--ru[e2[i].too]))st[++top]=e2[i].too;
}
}
int main()
{
read(n);read(m);
for(int i=;i<=n;i++)
{
read(len);
for(int j=;j<=len;j++)
read(x),v[i].push_back(x);
}
for(int i=;i<n;i++)
{
int flagg=;
for(int j=;j<min(v[i].size(),v[i+].size());j++)
if(v[i][j]!=v[i+][j])
{
if(v[i][j]<v[i+][j])add(next(v[i+][j]<<),next((v[i][j])<<)),add(v[i][j]<<,v[i+][j]<<);
else add(v[i][j]<<,next((v[i][j])<<)),add(next((v[i+][j])<<),v[i+][j]<<);
flagg=;break;
}
if(!flagg&&v[i].size()>v[i+].size())return puts("No"),;
// else add(next(v[i][min(v[i].size(),v[i+1].size())]<<1),next((v[i+1][min(v[i].size(),v[i+1].size())])<<1));
}
for(int i=;i<=m<<;i++)if(!dfn[i])tarjan(i);
for(int i=;i<=m;i++)
{
if(col[i<<]==col[next(i<<)]){printf("No\n");flag=;break;}
else op[col[i<<]]=col[next(i<<)],op[col[next(i<<)]]=col[i<<];
}
if(flag)return ;
for(int i=;i<=tot;i++)if(col[e[i].x]!=col[e[i].too])add2(col[e[i].too],col[e[i].x]),ru[col[e[i].x]]++;
topsort();
// for(int i=1;i<=tot;i++)printf("QAQ%d %d\n",e[i].x,e[i].too);
//if(rs[col[(i<<1)]]==rs[col[next(i<<1)]])return puts("No"),0;
for(int i=;i<=m;i++)if(rs[col[(i<<)]]!=)ans[++cnt]=i;
printf("Yes\n%d\n",cnt);
for(int i=;i<=cnt;i++)printf("%d ",ans[i]);
return ;
}
F：预处理出每个数每一位是0的那位左边最近的1和右边最近的1，用单调栈找出每个最大值所在的区间，统计答案即可。
T T一开始只预处理了20位查了好久错，浅谈状压写多了的后果
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=,inf=2e9;
int n,top;
int st[maxn],a[maxn],digit[maxn][],pre[maxn][],Pre[maxn],next[maxn][],Next[maxn],cnt[maxn];
ll ans;
inline void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
int main()
{
read(n);
for(int i=;i<=n;i++)
{
read(a[i]);
for(int x=a[i];x;x>>=)digit[i][++cnt[i]]=x&;
}
for(int j=,last=;j<=;j++,last=)
for(int i=;i<=n;i++)
{
if(!digit[i][j])pre[i][j]=last;
if(digit[i][j])last=i;
}
for(int i=;i<=n;i++)
for(int j=;j<=;j++)
if(!digit[i][j])
Pre[i]=max(Pre[i],pre[i][j]);
memset(next,,sizeof(next));
for(int j=,last=n+;j<=;j++,last=n+)
for(int i=n;i;i--)
{
if(!digit[i][j])next[i][j]=last;
if(digit[i][j])last=i;
}
memset(Next,,sizeof(Next));
for(int i=;i<=n;i++)
for(int j=;j<=;j++)
if(!digit[i][j])
Next[i]=min(Next[i],next[i][j]);
a[++n]=inf;
for(int i=;i<=n;i++)
{
for(;top&&a[i]>=a[st[top]];top--)
{
ans+=1ll*((i-)-st[top]+)*(st[top]-(st[top-]+)+);
ans-=1ll*(1ll*st[top]-1ll*max(st[top-]+,Pre[st[top]]+)+)*(min(i-,Next[st[top]]-)-st[top]+);
}
st[++top]=i;
}
printf("%lld\n",ans);
}