【CodeForces 624C】Graph and String
string and Codeforces Graph
2023-09-11 14:19:25 时间
题意
n个表示abc三个字符的点,所有a和b是相连的,所有b和c是相连的,所有相同的是相连的,现在给你n个点和他们之间的m条边,判断是否存在这样的字符串,存在则给出一个符合条件的。
分析
我的做法是找出所有的b,因为b是只和自己本身没有连接,所以有n-1个连线,然后找出第一个不是b的,然后所有和该点没有连线的都设置为c,有连线而不是b的就设置为a,然后再把该点设置为a。
接下来,根据题目条件,判断一下我设置出来的字符串成不成立。就是如果不相连接却是相同字母或者有b字母,还有如果相连接却是a和c,那都是不符合的。
代码
#include <stdio.h> #include <algorithm> #define F(a,b,c) for(int a=b;a<=c;a++) #define N 505 using namespace std; int n,m,a[N][N],l[N],u,v,ans,ok; char s[N]; int main() { scanf("%d%d",&n,&m); F(i,1,m){ scanf("%d%d",&u,&v); a[u][v]=a[v][u]=1; l[u]++; l[v]++; } F(i,1,n) if(l[i]==n-1) s[i]='b'; int i=1; while(s[i]=='b'&&i<=n) i++; F(j,1,n) if(!a[i][j]) s[j]='c'; else if(s[j]!='b') s[j]='a'; s[i]='a'; F(i,1,n&&ok!=-1) F(j,i+1,n) if(!a[i][j]&&(s[i]==s[j]||s[i]=='b') ||a[i][j]&&(s[i]=='a'&&s[j]=='c')) ok=-1; if(ok==-1) printf("No\n"); else { printf("Yes\n"); F(j,1,n) printf("%c",s[j]); } return 0; }
相关文章
- Leetcode: Find And Replace in String
- Leetcode: Unique Substrings in Wraparound String
- C# 之String以及浅拷贝与深拷贝
- Qt选择文件对话框-中文路径-转std::string
- HDU 4641 K-string
- CodeForces 159c String Manipulation 1.0
- node.js使用报错“The chunk argument must be of type string or an instance of Buffer or Uint8Array“
- 【Java】String,StringBuffer与StringBuilder的区别??
- JAVA字符串格式化-String.format()的使用 及 Android 中 string.xml 中 字符串格式转化
- c# String常用方法
- nyoj 198-数数 (python, string[::-1])
- [LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters 串联字符串的最大长度
- [CareerCup] 1.3 Permutation String 字符串的排列
- C++ string中的find()函数
- Weekly Contest 78-------->811. Subdomain Visit Count (split string with space and hash map)
- String.contains(object o)报出空指针异常