A判断输入的数字有没有覆盖1--n,n最大只有100,所以直接暴力
#include<iostream> #include<cstdio> #include<cstring> #include<map> using namespace std; map<int ,int>mmp; int n; int main(){ int i,j,k,b,a; while(scanf("%d",&n)!=EOF){ mmp.clear(); scanf("%d",&a); while(a--){ scanf("%d",&b); mmp[b]=1; } scanf("%d",&a); while(a--){ scanf("%d",&b); mmp[b]=1; } bool flag=0; for(i=1;i<=n;i++){ if(mmp[i]==0){ flag=1; break; } } if(flag==1){ printf("Oh, my keyboard!\n"); }else{ printf("I become the guy.\n"); } } return 0; }
B,如果数据量很大的话可能会用rmq吧,这里直接暴力判定
#include<iostream> #include<cstdio> #include<cstring> #include<map> using namespace std; bool vis1[3000]; bool mov[3000]; int main(){ int p,q,l,r,i,j,k,a,b,c,d; while(scanf("%d%d%d%d",&p,&q,&l,&r)!=EOF){ memset(vis1,0,sizeof(vis1)); memset(mov,0,sizeof(mov)); for(i=0;i<p;i++){ scanf("%d%d",&a,&b); for(j=a;j<=b;j++)vis1[j]=1; } for(i=0;i<q;i++){ scanf("%d%d",&a,&b); for(j=l;j<=r;j++){ c=a+j; d=b+j; for(k=c;k<=d;k++){ if(vis1[k]){ mov[j]=1; break; } } } } int res=0; for(i=l;i<=r;i++){ if(mov[i])res++; } cout<<res<<endl; } return 0; }
C,这一场最逗比的一题。题意是给出n,用1,2,3,4……n-1,n,这n个数字,只有加减乘算24,为什么逗比呢,看代码就知道了
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n; int main(){ int i,j,k; while(scanf("%d",&n)!=EOF){ if(n<=3){ printf("NO\n"); continue; } printf("YES\n"); if(n%2==0){ printf("3 * 4 = 12\n"); printf("12 * 2 = 24\n"); printf("24 * 1 = 24\n"); for(i=5;i<n;i+=2){ printf("%d - %d = 1\n",i+1,i); } for(i=5;i<n;i+=2){ printf("24 * 1 = 24\n"); } }else{ printf("5 * 4 = 20\n"); printf("20 + 2 = 22\n"); printf("22 + 3 = 25\n"); printf("25 - 1 = 24\n"); for(i=6;i<n;i+=2){ printf("%d - %d = 1\n",i+1,i); } for(i=6;i<n;i+=2){ printf("24 * 1 = 24\n"); } } } return 0; }
D,裸的2-sat,才发现当年的2-sat模板很久没用快发霉了,就当是来验模板吧。这里构图要注意一点:如果第I位数选择a集合时,第J 位数也要选a,同时也要连接一条边第j位选b时第i位也要选b
#include<iostream> #include<cstdio> #include <algorithm> #include<cstring> #include<map> using namespace std; const int inf=1<<31; const int nMax=300015; const int mMax=1000010; class edge{ public: int u,v,nex; };edge e[mMax],e2[mMax]; int k,head[nMax],head2[nMax],k2;//head[i]是以点i为起点的链表头部 int dfn[nMax],low[nMax],sta[nMax],top,atype,ans[nMax],belon[nMax],dep; //atype 强连通分量的个数 void addedge(int a,int b){//向图中加边的算法,注意加上的是有向边//b为a的后续节点既是a---->b // cout<<a<<" add "<<b<<endl; e[k].u=a; e[k].v=b; e[k].nex=head[a]; head[a]=k;k++; } void addedge2(int a,int b){ // cout<<a<<" 222add222 "<<b<<endl; e2[k2].u=a; e2[k2].v=b; e2[k2].nex=head2[a]; head2[a]=k2;k2++; } int tim1[nMax],tim2[nMax],cost[nMax],in[nMax],color[nMax],oppo[nMax],que[nMax];//囧 bool insta[nMax]; void Tarjan(int u){ int v,i; low[u]=dfn[u]=++dep; insta[u]=1; sta[++top]=u; for(i=head[u];i;i=e[i].nex){ v=e[i].v; if(!dfn[v]){ Tarjan(v); if(low[u]>low[v]) low[u]=low[v]; } else if(insta[v]&&low[u]>dfn[v]) low[u]=dfn[v]; } if(low[u]==dfn[u]){ atype++; do{ v=sta[top--]; insta[v]=false; belon[v]=atype; }while(u!=v); } return; } void buildremap(){ int i; for(i=1;i<k;i++){ if(belon[e[i].u]!=belon[e[i].v]){ addedge2(belon[e[i].v],belon[e[i].u]); in[belon[e[i].u]]++; } } } int n,m,a,b,num[100030]; map<int,int>mpp; void topsort(){ int i,l=0,r=0,u,v; for(i=1;i<=atype;i++){ if(in[i]==0){ que[r++]=i; // cout<<"inque "<<i<<endl; } } while(l<r) { u=que[l++]; if(color[u]==0){ color[u]=1; color[oppo[u]]=-1; // cout<<u<<" u="<<color[u]<<" oppou="<<oppo[u]<<" colorop="<<color[oppo[u]]<<endl; } v=head2[u]; while(v!=0){ if(--in[e2[v].v]==0){ // cout<<"inque "<<e2[v].v<<endl; que[r++]=e2[v].v; } v=e2[v].nex; } } for(i=1;i<=n;i++){ if(color[belon[i*2]]==1) ans[i]=1; } } void init(){ k=k2=1; dep=1; top=atype=0; memset(ans,0,sizeof(ans)); memset(color,0,sizeof(color)); memset(in,0,sizeof(in)); memset(insta,0,sizeof(insta)); //是否在栈中 memset(head,0,sizeof(head)); //静态链表头指针 memset(low,0,sizeof(low)); //Tarjan的low数组 memset(dfn,0,sizeof(dfn)); //Tarjan的dfn数组 memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量 memset(head2,0,sizeof(head2)); } bool judge(){ for(int i=1;i<=n;i++){ if(belon[i*2]==belon[i*2+1]){ return 0; } oppo[belon[i*2]]=belon[i*2+1]; oppo[belon[i*2+1]]=belon[i*2]; } return 1; } int main(){ int i,tmp; while(scanf("%d%d%d",&n,&a,&b)!=EOF){ mpp.clear(); for(i=1;i<=n;i++){ scanf("%d",&num[i]); mpp[num[i]]=i; } //i*2 A //i*2+1 B init(); bool flag=1; for(i=1;i<=n;i++){ tmp=num[i]; if(mpp[a-tmp]==0&&mpp[b-tmp]==0){ flag=0; break; } if(mpp[a-tmp]!=0&&mpp[b-tmp]==0){ addedge(i*2+1,i*2); addedge(i*2,mpp[a-tmp]*2); addedge(mpp[a-tmp]*2+1,i*2+1); } if(mpp[a-tmp]==0&&mpp[b-tmp]!=0){ addedge(i*2,i*2+1); addedge(i*2+1,mpp[b-tmp]*2+1); addedge(mpp[b-tmp]*2,i*2); } if(mpp[b-tmp]!=0&&mpp[a-tmp]!=0){ addedge(i*2,mpp[a-tmp]*2); addedge(mpp[a-tmp]*2+1,i*2+1); addedge(i*2+1,mpp[b-tmp]*2+1); addedge(mpp[b-tmp]*2,i*2); } } if(!flag){ printf("NO\n"); continue; } for(i=2;i<=2*n+1;i++){ if(!dfn[i])Tarjan(i); } if(judge()){ printf("YES\n"); buildremap(); topsort(); for(i=1;i<n;i++){ printf("%d ",1-ans[i]); }printf("%d\n",1-ans[n]); } else printf("NO\n"); } 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+