比赛链接
A:
水题,读懂题意即可
code:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<vector>
using namespace std;
int main()
{
string u;
int t;
cin>>t;
int sum = 2;
while(t--)
{
cin>>u;
for(int i=0;i<u.size();i++)
{
if(u[i]=='+')
{
sum++;
break;
}
}
sum++;
}if(sum==13)printf("%d\n",(sum+1)*100);
else printf("%d\n",sum*100);
return 0;
}
C:
求一个数被分解成质数的次幂乘积之后 的质数幂之和是否等于20,由于这个数为1e18,所以需要加一些剪枝,首先当次幂和大于20时就可以退出了,此时剩下的数如果不是1的话一定是NO,其次在寻找的过程中,如果当前状态的因子的(20-sum)次幂大于 当前剩下的数时,表明后面一定不满足题意,因此退出即可
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<math.h>
using namespace std;
const int maxn = 99999;
int factor(long long n,long long a[maxn],long long b[maxn],int &tot)
{
long long temp,i,now;
temp = (long long )((double)sqrt(n)+1);
tot =0 ;
now =n;
int sum2 = 0;
for(i=2; i<=temp; i++)
{
if(sum2>=20)break;
if(now%i==0)
{
a[++tot] = i;
b[tot] =0;
while(now%i==0)
{
++b[tot];
now/=i;
sum2++;
}
}
if(sum2>=20)break;
if((long long)pow(i+1,20-sum2)>now)
return false;
}
if(now!=1)
{
a[++tot] = now;
b[tot] = 1;
sum2++;
}
if(sum2>20)return false;
else return sum2;
}
int main()
{
long long n;
int tot =0;
cin>>n;
long long a[99999];
long long b[99999];
int ans = factor(n,a,b,tot);
// cout<<ans<<endl;
if(ans==20)printf("Yes\n");
else printf("No\n");
// for(int i=0; i<=tot; i++)
// {
// printf("%d ",a[i]);
// }
// printf("\n");
// for(int i=0; i<=tot; i++)
// {
// printf("%d ",b[i]);
// }
// printf("\n");
return 0;
}
D:dfs+博弈
题意:有一个小纸条,每次每个人都可以将其对折,如果对折后的正反面字母全一样则 剩下的字母标记的是谁谁获胜,否则平局,如果纸条长度是偶数可以继续对折,折到奇数的时候必须停止。dfs用状态号标记平局和谁胜利,如果轮到谁对折,那个人会尽可能的取dfs状态过程中有利于他的那一种状态
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n;
char a[600000],b[600000];
int dfs(int n,int state,char *a,char *b)
{
if(n%2==1)
{
int f = 0;
for(int i=0; i<n; i++)
{
if((a[i]=='A')|(b[i]=='A'))
{
if(f==1)f++;
else f =3;
}
if ( (a[i]=='B')|(b[i]=='B'))
{
if(f==3)f--;
else f = 1;
}
if(f==2)break;
}
return f;
}
int t1 = dfs(n/2,1-state,a,a+n/2);
int t2 = dfs(n/2,1-state,b,b+n/2);
if(state) return max(t1,t2);
else return min(t1,t2);
}
int main()
{
cin>>n;
cin>>a>>b;
int f = dfs(n,1,a,b);
if(f==2)
printf("Draw\n");
else if(f==1)
printf("Bob\n");
else printf("Alice\n");
return 0;
}
E:两个人从同一起点出发,沿圆形跑道运动,过程中可能会有停顿,问两人在过程中相遇几次?
计算出两人的距离总和除以跑道长度就是答案
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<vector>
using namespace std;
const int maxn = 99999;
int main()
{
long long l,t,va,vb,n, tti, ti, di;
long long ans = 0, a = 0, b = 0, rt = 0, dt;
scanf("%lld%lld%lld%lld%lld",&l,&t,&va,&vb,&n);
for(int i = 0; i < n; i++)
{
scanf("%lld%lld%lld",&tti,&ti,&di);
dt = ti - rt;
a += va * dt;
b += vb * dt;
if(tti == 1)
{
b += vb * di;
}
else
{
a += va * di;
}
rt = ti + di;
}
dt = t - rt;
a += va * dt;
b += vb * dt;
printf("%lld\n",(a+b)/l);
return 0;
}
G:bitset 巧妙应用
一个小男孩有一些玩具,
首先输入一个n和m,代表有n个玩具,m是代表接下里有m行
这m行表示 先输入一个01字符串,若满足左侧字符串的条件,他妈妈就会把该字符串右侧的子串中包含的玩具为他买下来,
通过一个01字符串来表示男孩是否有这些玩具,这个字符串在数据的最后一行输入
按照题意模拟即可,用set写了一发,但是超内存,
还是用bitset模拟比较方便,连输入都给省了
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
bitset<1100>a[5002],b[5002];
int main()
{
bitset<1100>o;
int n,m;
cin>>n>>m;
for(int i=1; i<=m; i++)
cin>>a[i]>>b[i];
cin>>o;
while(1)
{
int f = 1;
for(int i=1; i<=m; i++)
{
if( (o&a[i])==a[i] &&(o&b[i]) !=b[i])
{
o|=b[i];
f = 0;
}
}
if(f)break;
}
string ans = o.to_string();
cout<<string(ans.end()-n,ans.end())<<endl;
return 0;
}
set版
题目链接:
https://cn.vjudge.net/contest/208319#problem/G
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const int maxn = 99999;
int a[2000],b[2000];
char yy[2000];
set<int>o[4000],o2[4000];
int main()
{
set<int>have;
int n,m,u;
cin>>n>>m;
set<int>::iterator it,its;
for(int i=1; i<=m; i++)
{
scanf("%s",yy);
for(int j=0; j<n; j++)
{
if(yy[j]=='1')
o[i].insert(j+1);
}
// for(it=o[i].begin(); it!=o[i].end(); it++)
// {
// printf("%d",*it);
// }
// printf("\n");
scanf("%s",yy);
for(int j=0; j<n; j++)
{
if(yy[j]=='1')
o2[i].insert(j+1);
}
// for(it=o2[i].begin(); it!=o2[i].end(); it++)
// {
// printf("%d",*it);
// }
// printf("\n");
getchar();
}
scanf("%s",yy);
for(int i=0; i<n; i++)
{
if(yy[i]=='1')
have.insert(i+1);
}
// for(it=have.begin(); it!=have.end(); it++)
// {
// printf("%d ",*it);
// }
// printf("\n");
vector<int>temp;
set<int>tt;
int book2[4002]= {0};
int sum =0;
while(1)
{
// sum++;
// if(sum>10)break;
int f = 1;
for(int i=1; i<=m; i++)
{
if(!book2[i])
{ temp.clear();
set_intersection(have.begin(),have.end(),o[i].begin(),o[i].end(),back_inserter(temp));
// cout<<temp.size()<<endl;
// for(int u =0; u<temp.size(); u++)
// {
// printf("%d ",temp[u]);
// }
// printf("\n");
tt.clear();
for(int i=0; i<temp.size(); i++)
tt.insert(temp[i]);
if(tt==o[i])
{
f = 0;
book2[i] = 1;
temp.clear();
set_union(have.begin(),have.end(),o2[i].begin(),o2[i].end(),back_inserter(temp));
// for(int u =0; u<temp.size(); u++)
// {
// printf("%d ",temp[u]);
// }
// printf("%\n");
have.clear();
for(int i=0; i<temp.size(); i++)
have.insert(temp[i]);
}
}
}
if(f)break;
}
int book[2000]= {0};
for(it=have.begin(); it!=have.end(); it++)
{
book[*it]=1;
}
for(int i=1; i<=n; i++)
{
printf("%d",book[i]);
}
printf("\n");
return 0;
}