【Codeforces - Mail.Ru Cup 2018 Round 3 】A.B.C.D.E
前言
又是一个深夜场,本来想给biubiubiu_上个紫,没想到全程不在状态,最后四题,E甚至都没读题,赛后读题+写题直接半小时就过了,开场又是写错一个for循环的变量,导致7分钟才过掉a,之后看b感觉是一个好难的题,没什么思路,画个图想了一个做法,tle,打开代码一看一个O(1e9)的for循环摆在那里,赶紧优化掉,0:22过掉之后D过的比C多,想了一个nlogn的贪心然后wa了,反向贪心又wa了,仔细思考一下,01:31一个sort就过了,回头看C,**交互模拟题,不知道为什么比D过的少,直接写,写完交,返回未知错误,我以为是哪里不合法,一直找问题,最后加了个’\n’,就过了?2:28过掉C,宣告GG。赛后看D,sdHash题,分析一下复杂度,就是个nlogn,写完之后被卡ull的单hash,向pls学习了一波多hash的模板之后过掉了。
biubiubiu_ rating-=27 1888->1861
A. Determine Line
题意
给你n个序列,每个序列中的数在该序列中只出现一次,
输出在n个序列中都出现过的数
,每个数的值域为1-100
做法
先统计在第一个序列中出现过的,之后只保存所有之前出现过的就可以了。
我这个做法不是很好,我们其实只要统计哪些数出现过n次就可以了。
代码
#include<stdio.h>
int vis[105];
int vis2[105];
int main()
{
int n,x,y;
scanf("%d",&n);
scanf("%d",&x);
while(x--)
{
scanf("%d",&y);
vis[y]=1;
}
for(int i=1;i<=n-1;i++)
{
scanf("%d",&x);
for(int j=1;j<=100;j++) vis2[j]=0;
while(x--)
{
scanf("%d",&y);
vis2[y]=1;
}
for(int j=1;j<=100;j++)
{
if(vis[j]&&vis2[j]) vis[j]=1;
else vis[j]=0;
}
}
for(int i=1;i<=100;i++) if(vis[i]) printf("%d ",i);
printf("\n");
return 0;
}
B. Divide Candies
题意
给你一个n*n的方格,点(i,j)的权值为
问这个方格内有多少个数是m的倍数
做法
如上图蓝色阴影用蓝色块翻倍算,红色阴影用红色块翻倍算,紫色块自己算
代码
#include<stdio.h>
typedef long long ll;
int main()
{
ll n,m;
scanf("%lld%lld",&n,&m);
ll cnt=0;
for(ll i=1;i<=m;i++)
{
for(ll j=1;j<=m;j++)
{
ll tmp=i*i+j*j;
if(tmp%m==0) cnt++;
}
}
ll ans=((n/m)*(n/m))*cnt;
cnt=0;
for(ll i=(n-n%m)+1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
ll tmp=i*i+j*j;
if(tmp%m==0) cnt++;
}
}
ans+=2LL*cnt*(n/m);
cnt=0;
for(ll i=(n-n%m)+1;i<=n;i++)
{
for(ll j=(n-n%m)+1;j<=n;j++)
{
ll tmp=i*i+j*j;
if(tmp%m==0) cnt++;
}
}
ans+=cnt;
printf("%lld\n",ans);
return 0;
}
C. Pick Heroes
题意
有两个*,给你2*n个英雄,每个英雄有战斗力,两方轮流选择英雄
有m对英雄有捆绑关系,对于每对捆绑的英雄,若某一个被其中一方选择
则下个回合另一方必须选择捆绑的另一个英雄
要求尽量使所选英雄总战斗力值最大
如果最开始输入1,则表示你先选择,否则对手先选择
做法
首先如果我们先手,我们肯定先选完所有捆绑英雄中最战斗力大的那一个,
之后剩下的英雄中不断选择战斗力最高的就可以
如果我们后手,对手选择捆绑英雄的情况我们只能跟着选
否则我们直接转守为攻,选择完所有捆绑英雄,
之后再每次可以选的时候直接选剩下的英雄里战斗力最大的
代码
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 1e4+5;
int vis2[maxn];
int vis[maxn];
int l[maxn],r[maxn];
struct data
{
int id,num;
}a[maxn];
bool cmp(const data &a,const data &b)
{
return a.num<b.num;
}
int xx[maxn];
int main()
{
int n,m,x;
scanf("%d%d",&n,&m);
for(int i=1;i<=2*n;i++)
{
scanf("%d",&a[i].num);
a[i].id=i;
xx[i]=a[i].num;
}
sort(a+1,a+1+2*n,cmp);
for(int i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]);
int op;
scanf("%d",&op);
if(op==1)
{
int pos=1;
for(int i=1;i<=n;i++)
{
if(pos<=m)
{
if(xx[l[pos]]>xx[r[pos]])
{
vis[l[pos]]=1;
printf("%d\n",l[pos]);fflush(stdout);
}
else
{
vis[r[pos]]=1;
printf("%d\n",r[pos]);fflush(stdout);
}
pos++;
}
else
{
for(int j=2*n;j>=1;j--)
{
if(!vis[a[j].id])
{
vis[a[j].id]=1;
printf("%d\n",a[j].id);fflush(stdout);
break;
}
}
}
scanf("%d",&x);
vis[x]=1;
}
}
else
{
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
vis[x]=1;
int flag=0;
for(int j=1;j<=m;j++)
{
if(vis2[j]) continue;
if(l[j]==x)
{
vis2[j]=1;
flag=1;
vis[r[j]]=1;
printf("%d\n",r[j]);fflush(stdout);
break;
}
else if(r[j]==x)
{
vis2[j]=1;
flag=1;
vis[l[j]]=1;
printf("%d\n",l[j]);fflush(stdout);
break;
}
}
if(flag==0)
{
int ff=0;
for(int j=1;j<=m;j++)
{
if(!vis2[j])
{
ff=1;
vis2[j]=1;
if(xx[l[j]]>xx[r[j]])
{
vis[l[j]]=1;
printf("%d\n",l[j]);fflush(stdout);
}
else
{
vis[r[j]]=1;
printf("%d\n",r[j]);fflush(stdout);
}
break;
}
}
if(ff==0)
{
for(int j=2*n;j>=1;j--)
{
if(!vis[a[j].id])
{
vis[a[j].id]=1;
printf("%d\n",a[j].id);fflush(stdout);
break;
}
}
}
}
}
}
return 0;
}
D. Decorate Apple Tree
题意
给你一棵树每个叶子节点上都有一个颜色,
如果某个节点是好节点,要满足他子树内所有的叶子节点颜色不同
输出至少有k个点为好点最少需要多少种颜色
做法
每次选出的k个点最后只有一个点是有效的,也就是子树叶子节点最多的那个点
选n个点时一定是根,选n-1个点时一定是去掉根之后包含叶子节点最多的点
继续往下同理,而一棵树的点一共有n个,所以只要对n个节点按照包含叶子节点的个数排序
之后输出就可以了。
代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1e5+5;
vector<int> G[maxn];
vector<int> ans;
int sum[maxn];
void dfs(int u)
{
if(G[u].size()==0)
{
sum[u]=1;
return ;
}
for(int i=0;i<G[u].size();i++)
{
dfs(G[u][i]);
sum[u]+=sum[G[u][i]];
}
return ;
}
int main()
{
int n,x;
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
scanf("%d",&x);
G[x].push_back(i);
}
dfs(1);
sort(sum+1,sum+1+n);
for(int i=1;i<=n;i++) printf("%d ",sum[i]);
return 0;
}
E. Check Transcription
题意
给你一个01串s,一个字符串t,
做法
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
typedef unsigned long long ull;
const int maxn = 1e6+10;
char str[maxn],t[maxn];
template <int T>
struct StringHash
{
std::vector<std::vector<int>> ha, pw;
std::vector<int> M;
explicit StringHash(const std::string& s)
: StringHash(std::vector<int>(s.begin(), s.end())) {}
explicit StringHash(const std::vector<int>& vec)
{
pw = ha =
std::vector<std::vector<int>>(T, std::vector<int>(vec.size() + 1));
std::vector<int> C;
for (int i = 0; i < T; i++)
{
pw[i][0] = 1;
C.push_back(rand_int());
M.push_back(rand_int());
}
for (int z = 0; z < T; z++)
{
for (size_t i = 0; i < vec.size(); ++i)
{
ha[z][i + 1] = (1LL * ha[z][i] * C[z] + vec[i]) % M[z],
pw[z][i + 1] = 1LL * pw[z][i] * C[z] % M[z];
}
}
}
// hash value of interval [a, b)
std::vector<int> hash_interval(int a, int b)
{
std::vector<int> ret(T);
for (int z = 0; z < T; z++)
{
ret[z] = (ha[z][b] - 1LL * ha[z][a] * pw[z][b - a] % M[z] + M[z]) % M[z];
}
return ret;
}
static int rand_int() {
static std::mt19937 gen((std::random_device())());
static std::uniform_int_distribution<int> uid(1e8, 1e9);
return uid(gen);
}
};
int num[2];
int main()
{
scanf("%s%s",str,t);
StringHash<10> sh(t);
int lens=strlen(str);
int lent=strlen(t);
int ans=0;
for(int i=0;i<lens;i++)
{
if(str[i]=='0') num[0]++;
else num[1]++;
}
for(int i=1;i*num[1]<lent;i++)
{
if(((lent-i*num[1])%num[0])!=0) continue;
int len0=(lent-i*num[1])/num[0];
int len1=i;
vector<int> flag0,flag1;
int f0=-1,f1=-1;
int flag=0;
int tmp=0;
for(int j=0;j<lens;j++)
{
if(str[j]=='0')
{
if(f0==-1)
{
f0=1;
flag0=sh.hash_interval(tmp,tmp+len0);
tmp+=len0;
}
else
{
vector<int> tt=sh.hash_interval(tmp,tmp+len0);
if(tt!=flag0)
{
flag=1;
break;
}
else
{
tmp+=len0;
}
}
}
else
{
if(f1==-1)
{
f1=1;
flag1=sh.hash_interval(tmp,tmp+len1);
tmp+=len1;
}
else
{
vector<int> tt=sh.hash_interval(tmp,tmp+len1);
if(tt!=flag1)
{
flag=1;
break;
}
else
{
tmp+=len1;
}
}
}
}
if(flag0!=flag1&&flag==0) ans++;
}
printf("%d\n",ans);
return 0;
}