A暴力判断即可
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; bool inprim(int a){ int i; int k=sqrt(a); for(i=2;i<=k;i++){ if(a%i==0)return 1; } return 0; } int main(){ int n,i,j,k; while(scanf("%d",&n)!=EOF){ for(i=3;i<=n/2;i++){ if(inprim(i)&&inprim(n-i)){ printf("%d %d\n",i,n-i); break; } } } return 0; }
2贪心的思路,每次都先把所有人都运到需要到达的最低一层,去掉到达这一层的人之后继续网上运
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; bool inprim(int a){ int i; int k=sqrt(a); for(i=2;i<=k;i++){ if(a%i==0)return 1; } return 0; } int main(){ int n,i,j,k; while(scanf("%d",&n)!=EOF){ for(i=3;i<=n/2;i++){ if(inprim(i)&&inprim(n-i)){ printf("%d %d\n",i,n-i); break; } } } return 0; }
C,根据对输入的数据建图,然后dfs判断是否符合条件
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int nMax = 200007; const int mMax = 1000008; int n,m,nk,vis[nMax]; int smark[nMax],sum,marksort[nMax],vvv; class edge{ public: int v,nex; };edge e[mMax]; int k,head[nMax]; void addedge(int a,int b){ // cout<<a<<" add "<<b<<endl; e[k].v=b; e[k].nex=head[a]; head[a]=k;k++; } char str1[nMax][54],str2[nMax][54]; int ipt[100012]; bool dfs(int loc){ vis[loc]=1; if(loc==ipt[n]||loc==ipt[n]+n)return 1; for(int i=head[loc];i;i=e[i].nex){ int v=e[i].v; if(vis[v]==1)continue; if(dfs(v))return 1; }return 0; } int main(){ int i; while(scanf("%d",&n)!=EOF){ for(i=1;i<=n;i++){ scanf("%s%s",str1[i],str2[i]); } for(i=1;i<=n;i++){ scanf("%d",&ipt[i]); } if(n==1){ printf("YES\n"); continue; } k=1; memset(head,0,sizeof(head)); addedge(0,ipt[1]); addedge(0,ipt[1]+n); for(i=1;i<n;i++){ int j=i+1; if(strcmp(str1[ipt[i]],str1[ipt[j]])<0){ addedge(ipt[i],ipt[j]); } if(strcmp(str1[ipt[i]],str2[ipt[j]])<0){ addedge(ipt[i],ipt[j]+n); } if(strcmp(str2[ipt[i]],str1[ipt[j]])<0){ addedge(ipt[i]+n,ipt[j]); } if(strcmp(str2[ipt[i]],str2[ipt[j]])<0){ addedge(ipt[i]+n,ipt[j]+n); } } memset(vis,0,sizeof(vis)); if(dfs(0)){ printf("YES\n"); }else printf("NO\n"); } return 0; }
D 很有意思的一题,一直以为是用floyd,后来发现不仅效率过不去,而且算法有漏洞。正确办法是,先对图求出prim最小生成树。再对最小生成树进行dfs求出任意两点间距,如果求出的这个间距和输入的矩阵相等则输出yes。要注意处理n==1的情况!一个点不是树但是空树是树!
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const long long inf=1e+20; const int nMax=2002; const int mMax=8000003; long long map[2002][2002],n,ans; long long dis[2002]; class edge{ public: int u,v,nex,w; };edge e[mMax]; int k,head[nMax];//head[i]是以点i为起点的链表头部 void addedge(int a,int b,int c){//向图中加边的算法,注意加上的是有向边//b为a的后续节点既是a---->b // cout<<a<<" add "<<b<<" with "<<c<<endl; e[k].u=a; e[k].v=b; e[k].w=c; e[k].nex=head[a]; head[a]=k;k++; } int fff[nMax]; void prim(){ // 自己的prim模板。 int i, j, now,aaa,bbb; long long min_node, min_edge; for(i = 0; i < n; i ++) dis[i] = inf; now = 0; ans = 0; for(i = 0; i < n-1; i ++){ dis[now] = -1; // 将dis[]的值赋-1,表示已经加入生成树中。 min_edge = inf; for(j = 0; j < n; j ++) // 更新每个顶点所对应的dis[]值。 if(now != j && dis[j] >= 0){ if(map[now][j]<dis[j]){ dis[j]=map[now][j]; fff[j]=now; } if(dis[j] < min_edge){ min_edge = dis[j]; min_node = j; // cout<<j<<"de\n"; } } now = min_node; aaa=now; bbb=fff[now]; ans += min_edge; addedge(aaa,bbb,min_edge); addedge(bbb,aaa,min_edge); } } bool vis[2002]; int paint[2002][2002],loc; void dfs(int a,int w){ vis[a]=1; for(int i=head[a];i;i=e[i].nex){ int v=e[i].v; if(!vis[v]){ paint[v][loc]=w+e[i].w; dfs(v,w+e[i].w); } } } int main(){ int i,j; bool flag; while(scanf("%d",&n)!=EOF){ flag=0; for(i=0;i<n;i++){ for(j=0;j<n;j++){ scanf("%I64d",&map[i][j]); if(map[i][j]!=0){ flag=1; } } } if(n==1){ if(map[0][0]==0) printf("YES\n"); else printf("NO\n"); continue; } if(!flag){ printf("NO\n"); continue; } flag=0; for(i=0;i<n;i++){ if(map[i][i]!=0){ flag=1; continue; } } if(flag){ printf("NO\n"); continue; } k=1; memset(head,0,sizeof(head)); prim(); memset(paint,0,sizeof(paint)); for(i=0;i<n;i++){ memset(vis,0,sizeof(vis)); loc=i; dfs(i,0); } flag=0; for(i=0;i<n&&!flag;i++){ for(j=0;j<n&&!flag;j++){ // cout<<paint[i][j]<<" "; if(map[i][j]!=paint[i][j]){ flag=1; break; } }//cout<<endl; } if(flag){ printf("NO\n"); } else{ printf("YES\n"); } } }
相关推荐
Codeforces Round #723 (Div. 2).md
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
传送门 题意: 一个长度为n的数组,为删除一些数后,剩下的数能否构成长度大于3的回文数组 思路: 只要能找到两个相等的数,且他们的间距大于2即可 o(n^2)的暴力就能过 比赛时写了一个o(n)的 就是把所有相等的数放到...
传送门 题意: 给一个数k,构造一个矩阵 用上面那个代码跑出来的值dp[n][m],和找到一个走法,从(1,1)走到(n,m)路径上的值相与的最大值ans,他们的差值是k 思路: 构造一个2*3的就可以了 ...
B. K-th Beautiful String 题目链接-B. K-th Beautiful String 题目大意 长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
传送门 题意: 给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: ...
C. Ehab and Path-etic MEXs 题意 给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。...
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<=st[y]<...
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 ...
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
A. EhAb AnD gCd 题目链接-A. EhAb AnD gCd 题目大意 输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,...
传送门 A. EhAb AnD gCd 直接输出1,n-1即可 #include #include #include #include #include #include #include #include #include #include #define pb push_back #define lb lower_bound ...con
传说门 刚好今晚是中国场! 其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a.a 题意:三个数组,求(x-y)(x-y)+(x-z)(x-z)+(y-z)*(y-z)的最小值 题解:6nlogn,先sort三个数组a,b,c, 六次枚举二...
B. Yet Another Palindrome Problem 题目链接-B. Yet Another Palindrome Problem 题目大意 给一个长为n(≤5000)的数组,问是否存在一个长度至少为3的子序列是回文的,子序列的数可以不连续但是相对顺序不可变 ...
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
题目传送 题目大意: 定义一个函数:f(x,y) = (x|y)-y 将数组排序,使得最后结果最大。 分析: 手写几组数据后发现,最后的结果只和第一个数字有关,也就是只需要确定第一个数字就可以了。将所有数字看成2进制,从...