Codeforces Round #469 (Div. 2)
难得的下午场，又掉分了。。。。
Problem A: 怎么暴力怎么写。
#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define read(x) scanf("%d",&x)
#define sread(x) scanf("%s",x)
#define dread(x) scanf("%lf",&x)
#define lread(x) scanf("%lld",&x)
using namespace std; typedef long long ll;
const int inf=0x3f3f3f3f;
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+;
const int M=; int n; int l,r,m;
int main()
{
read(l); read(r); read(m);
int ret=min(l,r);
int ans=;
ans+=ret*;
l-=ret;
r-=ret;
ret=min(l,m);
ans+=ret*;
l-=ret;
m-=ret;
ret=min(r,m);
ans+=*ret;
r-=ret;
m-=ret;
if(m&) m--;
printf("%d\n",ans+m);
return ;
}
/*
*/
Problem B:
题目大意：把一段信息分别拆成 A里的n段和 B里的m段，A和B都重新组合一下，最多有多少个信息片段相同。
思路：刚开始以为拆了之后是无序的，发现不会，重读了一下题，原来就是相邻的。。。。 处理一下前缀和，类似于
two point 搞一搞就好啦。
#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define read(x) scanf("%d",&x)
#define sread(x) scanf("%s",x)
#define dread(x) scanf("%lf",&x)
#define lread(x) scanf("%lld",&x)
using namespace std; typedef long long ll;
const int inf=0x3f3f3f3f;
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+;
const int M=; int n,m;
ll a[N],b[N],sum1[N],sum2[N];
int main()
{
read(n); read(m);
for(int i=;i<=n;i++)
lread(a[i]);
for(int i=;i<=m;i++)
lread(b[i]); for(int i=;i<=n;i++)
sum1[i]=sum1[i-]+a[i];
for(int i=;i<=m;i++)
sum2[i]=sum2[i-]+b[i]; int p1=,p2=,ans=;
while(p1<=n && p2<=m)
{ while(sum1[p1]!=sum2[p2])
{
while(sum1[p1]<sum2[p2])
p1++; while(sum1[p1]>sum2[p2])
p2++; }
ans++;
p1++;
p2++;
}
printf("%d\n",ans);
return ;
}
/*
*/
Problem C:
题意：给你一个0,1组成的串，要求你按时间顺序任意组合成若干个串，要求每个串首尾都是0，且0和1不相邻。
思路：想了5分钟就会写了，从前往后处理，如果当前是0，且以前的串里最后一位没有1的，那么新开一个串，
否则接在以前那个串的后边，如果当前的是0，且以前的串里最后一位没有0的，输出-1，否则接在以前那个串
的后边，最后判断一下所有串的首尾是不是都是0。
#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define read(x) scanf("%d",&x)
#define sread(x) scanf("%s",x)
#define dread(x) scanf("%lf",&x)
#define lread(x) scanf("%lld",&x)
using namespace std; typedef long long ll;
const int inf=0x3f3f3f3f;
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+;
const int M=; char s[N];
int cnt[N],tot,n;
vector<int> ans[N];
vector<int> num0,num1;
int main()
{
sread(s+);
n=strlen(s+);
for(int i=;i<=n;i++)
{
if(s[i]=='')
{
if(!num1.size())
{
ans[tot].push_back(i);
num0.push_back(tot);
tot++;
}
else
{
int id=num1[num1.size()-];
num1.pop_back();
ans[id].push_back(i);
num0.push_back(id);
}
}
else
{
if(!num0.size())
{
puts("-1");
return ;
}
else
{
int id=num0[num0.size()-];
num0.pop_back();
ans[id].push_back(i);
num1.push_back(id);
}
}
}
if(num1.size())
{
puts("-1");
return ;
}
printf("%d\n",tot);
for(int i=;i<tot;i++)
{
printf("%d ",ans[i].size());
for(int j:ans[i])
printf("%d ",j);
puts("");
}
return ;
}
/*
*/
Problem D:
题意：有n个数，数i在 2*i-1的位置，每次操作将最后一个元素，放到与其最近的空位置，知道1-n位置被填满。
思路：刚开始想找规律，找了半天没找到，后来发现前n个位置里边如果本来就有元素，那么这个元素一定是不会
变的，原来空着的地方全部都是大于n位置上的元素跳过来的，比如说第一个空位上最后的元素肯定是从位置在n+1
上的元素跳过来的，如果n+1还是空位则递归处理，否则，这个元素就是第一个空位的元素。
最后写的太慌了，调了半天没有A掉，赛后马上就A了，气死了。。。。。
#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define read(x) scanf("%d",&x)
#define sread(x) scanf("%s",x)
#define dread(x) scanf("%lf",&x)
#define lread(x) scanf("%lld",&x)
using namespace std; typedef long long ll;
const int inf=0x3f3f3f3f;
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+;
const int M=; ll n,q,cnt=;
ll dfs(ll x,ll l,ll r)
{
if(x&)
return x;
if(l&)
{
ll cnt=(x-l)/+;
ll num=(r+)/-(l+)/+;
return dfs(l+num+cnt-,l+num,r);
}
else
{
ll cnt=(x-l)/+;
ll num=(r+)/-(l+)/+;
return dfs(l+num+cnt-,l+num,r);
}
}
int main()
{
lread(n); lread(q);
for(int i=;i<=q;i++)
{
ll x; lread(x);
ll ans=dfs(x,,*n-);
printf("%lld\n",(ans+)/);
}
return ;
}
/*
*/
Problem E:
题意：这个题意我真的讲不来。。。。。但是赛后补的时候感觉这个题比D简单。。
思路：对于c1,c2两个信息中心来说来说，如果t[c1] 是 t[c2] 前面一个时间，那么c1向c2建一条边，表明c1动了，c2必须动，
如果t[c2] 是 t[c1]前面一个时间，那么c2向c1建一条边，表明c2动了，c1必须动。 直接跑一个强连通分量，缩点之后变成一个
拓扑图，对于每个强连通分量来说，只有没有出度的才有机会成为答案，那么在没有出度的里面找最小值就好啦。
#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define read(x) scanf("%d",&x)
#define sread(x) scanf("%s",x)
#define dread(x) scanf("%lf",&x)
#define lread(x) scanf("%lld",&x)
using namespace std; typedef long long ll;
const int inf=0x3f3f3f3f;
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=3e6+;
const int M=; int n,m,h,dindex,all,cnt,t[N],dfn[N],low[N],st[N],id[N],dg[N];
bool inst[N];
vector<int> edge[N],ans[N]; void tarjan(int v)
{
dindex++;
dfn[v]=low[v]=dindex;
st[all++]=v; inst[v]=true;
for(int nx:edge[v])
{
if(!dfn[nx])
{
tarjan(nx);
low[v]=min(low[v],low[nx]);
}
else if(inst[nx]) low[v]=min(low[v],low[nx]);
}
if(dfn[v]==low[v])
{
cnt++;
while()
{
int cur=st[--all];
inst[cur]=false;
id[cur]=cnt;
ans[cnt].push_back(cur);
if(cur==v) break;
}
}
} int main()
{
read(n); read(m); read(h);
for(int i=;i<=n;i++)
read(t[i]);
for(int i=;i<=m;i++)
{
int c1,c2;
read(c1); read(c2);
if((t[c1]+)%h==t[c2])
edge[c1].push_back(c2);
if((t[c2]+)%h==t[c1])
edge[c2].push_back(c1);
} for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i); for(int i=;i<=n;i++)
for(int j:edge[i])
if(id[i]!=id[j])
dg[id[i]]++; int ret=inf,pos;
for(int i=;i<=cnt;i++)
if(dg[i]== && ans[i].size()<ret)
ret=ans[i].size(),pos=i; printf("%d\n",ret);
for(int i:ans[pos])
printf("%d ",i);
puts("");
return ;
}
/*
*/