Div1A / 2C. Make Nonzero Sum
令最后每个\(a_i\)的系数为\(c_i\)(\(c_i=1/-1\))，发现只要满足\(c_1=1\)(下标从1开始)，且c中没有两个-1相连，就一定能找出一种划分方式。那我们先令所有\(c_i\)都为1，再进一步把一些1改成-1。如果全是1时序列的和sum已经是0，那么就已经找到一个答案了。否则我们只会把\(a_i=1/-1\)的位置的系数改成-1，当\(sum>0\)时改\(a_i=1\)的i的系数，否则改\(a_i=-1\)的i的系数。发现每改变一个位置的系数，sum的变化量都是2，所以sum也必须是偶数，否则无解。然后就是把尽量多的能修改系数的位置的系数改成-1，最后保留其中的\(|\frac{sum}2|\)个就可以了。可以用贪心或一个简单的dp完成。
时间复杂度\(O(n)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
int t,n,a[200010],good[200010],swit[200010];
pii dp[200010][2];
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n;
int sum=0;
rep(i,n) scanf("%d",&a[i]),sum+=a[i],good[i]=0;
if(sum%2!=0)
{
puts("-1");
continue;
}
if(sum>0)
{
rep(i,n) if(a[i]==1)
good[i]=1;
}
else
{
sum=-sum;
rep(i,n) if(a[i]==-1)
good[i]=1;
}
sum/=2;
rep(i,n+3) rep(j,2) dp[i][j]=mpr(-1,-1);
dp[0][0]=mpr(0,-1);
rep(i,n) rep(j,2) if(dp[i][j].fi>-1)
{
dp[i+1][0]=max(dp[i+1][0],mpr(dp[i][j].fi,j));
if(j==0&&good[i]&&i>0) dp[i+1][1]=max(dp[i+1][1],mpr(dp[i][j].fi+1,j));
}
if(dp[n][0].fi<sum&&dp[n][1].fi<sum) puts("-1");
else
{
int i=n,j=(dp[n][0].fi>=sum ? 0:1);
while(true)
{
swit[i-1]=j;
if(i==1) break;
j=dp[i][j].se;--i;
}
int cnt=0;
rep(i,n)
{
cnt+=swit[i];
if(cnt>sum) swit[i]=0;
}
vector <pii> ans;
rep(i,n)
{
int p=i;
while(p+1<n&&swit[p+1]==(swit[p]^1)) ++p;
ans.pb(mpr(i,p));
i=p;
}
cout<<ans.size()<<endl;
rep(i,ans.size()) printf("%d %d\n",ans[i].fi+1,ans[i].se+1);
}
}
termin();
}
1B / 2D. Factorial Divisibility
发现两个\(1!\)可以合成一个\(2!\)，三个\(2!\)可以合成一个\(3!\)…… 我们从1枚举到p-1，每次尽量地把i合并到i+1，最后如果\(1!,2!\cdots (p-1)!\)还有剩余的话，仔细想想发现是不可能整除的。\(p!\)及以上如果有剩余那当然是可以整除的了。
时间复杂度\(O(p)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
int n,x,a[500010];
int main()
{
fileio();
cin>>n>>x;
int xx;
rep(i,n)
{
scanf("%d",&xx);
++a[xx];
}
repn(i,x-1)
{
if(a[i]%(i+1)>0)
{
puts("No");
termin();
}
a[i+1]+=a[i]/(i+1);
}
puts("Yes");
termin();
}
1C / 2E. Wish I Knew How to Sort
脑筋急转弯，感觉非常类似于atcoder的风格。好像有不少人会D但不会这个C
令序列中0的数量为x，则我们想要的序列是前x个为0，后n-x个为1，也就是要把初始序列中前x个位置中的1，以及后n-x个位置中的0都干掉。这两种类型的数量永远是相同的。假设前x个位置中有k个1(初始的k用一次遍历求出)，则一次操作能把k减1的概率是\(\frac{k^2}{\binom n2}\)，所以期望\(\frac{\binom n2}{k^2}\)次操作才能把k减1。所以枚举所有可能的k，对这个值求和即可。
时间复杂度\(O(nlogn)或O(n)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
const LL MOD=998244353;
LL qpow(LL x,LL a)
{
LL res=x,ret=1;
while(a>0)
{
if((a&1)==1) ret=ret*res%MOD;
a>>=1;
res=res*res%MOD;
}
return ret;
}
LL t,n,a[200010];
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n;
rep(i,n) scanf("%lld",&a[i]);
LL c0=0;
rep(i,n) if(a[i]==0) ++c0;
LL bad=0;
rep(i,c0) if(a[i]==1) ++bad;
LL full=n*(n-1)/2%MOD,ans=0;
for(LL i=bad;i>0;--i)
{
LL goods=i*i%MOD,add=full*qpow(goods,MOD-2)%MOD;
(ans+=add)%=MOD;
}
printf("%lld\n",ans);
}
termin();
}
1D / 2F. The Beach
我咋就fst呢了！？
(自行脑补痛苦吼叫)
首先如果一开始就有连续的两个空地，那答案就是0。
剩下的情况就是我最后占用的两个位置一开始都被占据，或者其中有一个一开始被占据。其中前者的两个位置一开始不可能属于同一张床，因为这样的话我们可以跟踪那张被移走的床，并让他把现在占据的位置让给我们。这样还能少点步数(\([1]\))。
"让出位置"的过程到底是什么样的？其实是一条路径，满足其中一端是一个空地，其他部分都是首尾相接的床，像这样：
令路径的方向为从空地指向床(只是用来便于理解)。每往路径里加一张床会有一个代价(p或q)，由新的床和上一张床的位置决定。
枚举我们最后占用的两个位置，如果其中有一个是空地，那么需要找出另一个位置到任意一个空地的最短路。注意到路径每加一张床，路径终点的横纵坐标之和的奇偶性都不会改变，所以不会出现最短路起点(注意上面说的最短路的方向)是需要留出的那个空地的情况。
如果两个位置都不是空地，那么我们需要考虑它们两个的最短路相交的情况。但其实相交一定是不优的，枚举了也无所谓。这是因为如果它们相交，根据上面说的横纵坐标之和的奇偶性都不会改变的性质，路径上肯定有某张床的两个位置都要被移走，但是在\([1]\)处我们就说了这是不优的。显然，这两条最短路的终点也不会重合，所以直接用它们的长度之和更新答案就行了。
时间复杂度\(O(nmlog(nm))\)。
比赛的时候没仔细想奇偶性不变的性质，于是代码里就记录了到每个点的最短路、次短路和次次短路，代码巨长，还有一个地方没入队导致fst了。
我写的Dijkstra没有记录每个点是否已经转移过，但是每个点的入度都不大所以不影响复杂度。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
LL n,m,p,q,dx[]={-1,1,0,0},dy[]={0,0,-1,1},ans=1e18;
string s[300010];
char c[300010];
vector <pair <LL,pii> > dist[3][300010];
vector <pii> mat[300010];
priority_queue <pair <pair <LL,pii>,pii>,vector <pair <pair <LL,pii>,pii> >,greater <pair <pair <LL,pii>,pii> > > qq;
bool out(LL x,LL y){return x<0||x>=n||y<0||y>=m;}
void upd(LL tox,LL toy,pair <LL,pii> val,LL fx,LL fy)
{
if(fx!=tox&&fy!=toy) val.fi+=p;else val.fi+=q;
bool hv=false;
rep(i,3)
{
if(dist[i][tox][toy].se==val.se)
{
if(dist[i][tox][toy].fi>val.fi)
{
dist[i][tox][toy].fi=val.fi;
if(!hv) qq.push(mpr(val,mpr(tox,toy)));
}
return;
}
if(val.fi<dist[i][tox][toy].fi)
{
if(!hv)
{
hv=true;
qq.push(mpr(val,mpr(tox,toy)));
}
swap(val,dist[i][tox][toy]);
}
}
}
void check(int x,int y,int xx,int yy)
{
rep(i,3) if(dist[i][x][y].fi<1e18&&dist[i][x][y].se!=mpr(xx,yy))
ans=min(ans,dist[i][x][y].fi);
}
void check2(int x,int y,int xx,int yy)
{
rep(i,3) if(dist[i][x][y].fi<1e18&&dist[i][x][y].se!=mpr(xx,yy))
rep(j,3) if(dist[j][xx][yy].fi<1e18&&dist[j][xx][yy].se!=mpr(x,y))
if(dist[i][x][y].se!=dist[j][xx][yy].se) ans=min(ans,dist[i][x][y].fi+dist[j][xx][yy].fi);
}
int main()
{
fileio();
cin>>n>>m>>p>>q;
rep(i,n)
{
scanf("%s",c);
s[i]=c;
}
rep(i,3) rep(j,n) rep(k,m) dist[i][j].pb(mpr(1e18,mpr(-1,-1)));
rep(j,n) rep(k,m) mat[j].pb(mpr(0,0));
rep(i,n) rep(j,m)
{
if(s[i][j]=='U') mat[i][j]=mpr(i+1,j),mat[i+1][j]=mpr(i,j);
else if(s[i][j]=='L') mat[i][j]=mpr(i,j+1),mat[i][j+1]=mpr(i,j);
}
rep(i,n) rep(j,m) if(s[i][j]=='.')
{
rep(k,4)
{
int xx=i+dx[k],yy=j+dy[k];
if(out(xx,yy)|| !isalpha(s[xx][yy])) continue;
upd(mat[xx][yy].fi,mat[xx][yy].se,mpr(0LL,mpr(i,j)),i,j);
}
}
while(!qq.empty())
{
pair <pair <LL,pii>,pii> f=qq.top();qq.pop();
auto val=f.fi;
int x=f.se.fi,y=f.se.se;
rep(i,4)
{
int xx=x+dx[i],yy=y+dy[i];
if(out(xx,yy)|| !isalpha(s[xx][yy])) continue;
upd(mat[xx][yy].fi,mat[xx][yy].se,val,x,y);
}
}
rep(i,n) rep(j,m)
{
int ii=i+1,jj=j;
if(!out(ii,jj)&&s[i][j]!='U'&&s[i][j]!='#'&&s[ii][jj]!='#')
{
if(s[i][j]=='.'&&s[ii][jj]=='.') ans=0;
else
{
if(s[i][j]=='.') check(ii,jj,i,j);
else if(s[ii][jj]=='.') check(i,j,ii,jj);
else check2(i,j,ii,jj);
}
}
ii=i;jj=j+1;
if(!out(ii,jj)&&s[i][j]!='L'&&s[i][j]!='#'&&s[ii][jj]!='#')
{
if(s[i][j]=='.'&&s[ii][jj]=='.') ans=0;
else
{
if(s[i][j]=='.') check(ii,jj,i,j);
else if(s[ii][jj]=='.') check(i,j,ii,jj);
else check2(i,j,ii,jj);
}
}
}
if(ans>=1e18) puts("-1");
else cout<<ans<<endl;
termin();
}
个人属于比较稳重的类型，这种拼手速的场次不是很打的来……
标签：题解,rep,Codeforces,ii,mpr,jj,fi,Div,define From： https://www.cnblogs.com/legendstane/p/Codeforces-Round-829-div-1-div-2-1753-solution.html