赛后当练习做的,估摸着真实参加的话也只能出前两题,姿势水平还有待提高
A,要注意的trick有5个棒棒都相同的情况和6个棒棒都相同的情况,代码写的很乱
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int mark[10]; int main(){ int num[10],i,j,k,n,m; while(cin>>num[0]){ memset(mark,0,sizeof(mark)); mark[num[0]]++; for(i=1;i<6;i++){ cin>>num[i]; mark[num[i]]++; } bool flag1=0,flag2=0; for(i=1;i<=9;i++){ if(mark[i]>=4){ flag1=1; if(mark[i]==6){ flag2=1; } } if(mark[i]==2){ flag2=1; } } if(!flag1){ cout<<"Alien\n"; }else{ if(flag2){ cout<<"Elephant\n"; }else{ cout<<"Bear\n"; } } } return 0; }
B,对所有难度排序之后,查看有没有 两个相同的难度*2 或者是 三个相同的难度*1,不满足则输出no,满足的话再分情况讨论。
#include<iostream> #include<cstring> #include<cstdio> #include<map> #include<algorithm> using namespace std; class num{ public: int a,b;}seq[2006]; int cmp(const void *a,const void *b){ num *aa=(num*)a; num *bb=(num*)b; return(((aa->a)>(bb->a))?1:-1); } int rright[2006]; int main(){ int i,j,k,n,res; while(cin>>n){ res=0; for(i=0;i<n;i++){ cin>>seq[i].a; seq[i].b=i+1; } qsort(seq,n,sizeof(seq[0]),cmp); memset(rright,0,sizeof(rright)); for(i=n-2;i>=0;i--){ if(seq[i].a==seq[i+1].a){ rright[i]=rright[i+1]+1; } } bool flag3=0; res=0; int loc[2003]; int l3; for(i=0;i<n;i++){ if(rright[i]>=2){ l3=i; flag3=1; break; } if(rright[i]==1){ loc[res]=i; res++; } } if(!flag3&&res<2){ cout<<"NO"<<endl; }else{ cout<<"YES"<<endl; for(i=0;i<n-1;i++){ cout<<seq[i].b<<" "; }cout<<seq[n-1].b<<endl; if(flag3){ for(i=0;i<l3;i++){ cout<<seq[i].b<<" "; } cout<<seq[l3+1].b<<" "<<seq[l3].b<<" "<<seq[l3+2].b; for(i=l3+3;i<n;i++){ cout<<" "<<seq[i].b; }cout<<endl; for(i=0;i<l3;i++){ cout<<seq[i].b<<" "; } cout<<seq[l3+2].b<<" "<<seq[l3].b<<" "<<seq[l3+1].b; for(i=l3+3;i<n;i++){ cout<<" "<<seq[i].b; }cout<<endl; } else{ for(i=0;i<loc[0];i++){ cout<<seq[i].b<<" "; }cout<<seq[loc[0]+1].b<<" "<<seq[loc[0]].b; for(i=loc[0]+2;i<n;i++){ cout<<" "<<seq[i].b; }cout<<endl; for(i=0;i<loc[1];i++){ cout<<seq[i].b<<" "; }cout<<seq[loc[1]+1].b<<" "<<seq[loc[1]].b; for(i=loc[1]+2;i<n;i++){ cout<<" "<<seq[i].b; }cout<<endl; } } } return 0; }
C,很容易发现每层的卡片数n都满足(n+1)%3==0;然后数学推导出如果n个卡片存在k层则有
3*a1-1+3*a2-1+3*a3-1+ +3*ak-1=n
===>3*(a1+a2+a3+ +ak)=n+k
===>a1+a2+a3+ +ak=(n+k)/3
所以有n+k必须被3整除
(n+k)/3必须大于等于f(k)=1+2+3+ +k
因为这里f(k)增长很快,所以枚举很快就会跳出
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int main(){ long long n,k,i,j,res; while(cin>>n){ res=0; for(k=1;k<n;k++){ if((n+k)%3!=0)continue; if((n+k)/3<(k*(k+1)/2))break; res++; } cout<<res<<endl; } return 0; }
D最没技术含量的一题,做差+kmp模板就过了
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int nMax=200050; const int mMax=200005; int text[mMax],pat[nMax]; int lent,lenp,next[nMax]; void get_next(){ int i,j=-1; next[0]=-1; for(i=1;i<=lenp;i++){ //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符 while(j>-1&&pat[j+1]!=pat[i])j=next[j]; if(pat[j+1]==pat[i])j++; next[i]=j; } } int KMP(){ int ans=0,i=0,j=-1; get_next(); for(i=0;i<lent;i++){ while(j!=-1&&pat[j+1]!=text[i]){ j=next[j]; } if(pat[j+1]==text[i])j=j+1; if(j==lenp-1)ans++; //找到一个匹配 } return ans; } int main(){ int i,j,k; while(scanf("%d%d",&lent,&lenp)!=EOF){ for(i=0;i<lent;i++){ scanf("%d",&text[i]); } for(i=0;i<lenp;i++){ scanf("%d",&pat[i]); } lent--,lenp--; if(lenp==0){ cout<<lent+1<<endl; continue; } if(lent==0){ cout<<"ssss"<<endl; continue; } for(i=0;i<lent;i++){ text[i]=text[i+1]-text[i]; } for(i=0;i<lenp;i++){ pat[i]=pat[i+1]-pat[i]; } cout<<KMP()<<endl; } return 0; }
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...
传说门 刚好今晚是中国场! 其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a....#pragma GCC optimize(2) #include #define ll long long #define endl '\n' using namespace std; const int manx=
C(n-2,i-1)*C(j-1,n-2)*(i-1) __ j: n-1 -> m 我们发现内层循环,每次只是j加一,我们就可以只用一次组合数剩下的用差量表示 对于外层循环同理 只有(i-1) * C(n-2,i-1) i会每次加一。我们也只算一次剩下的用差量...
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<...const int M = 2e5+