CodeForces1230

绝地灬酷狼 2023-06-02 12:52 5阅读 0赞

# CodeForces1230A #

[CodeForces1230A][]  
题目并不难,只需要注意不要犯智障错误即可.  
智障错误包括但不限于:以为要两两一组分两组和判断两部分是否相等时总和与总和-当前集合比较...

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define one first #define two second #define rint read<int> #define int long long #define pb push_back #define db double using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } int can[6] , sum ; inline bool check (int x , int y) { return ( sum - can[x] - can[y] ) == ( can[x] + can[y] ) ; } signed main (int argc , char * argv[]) { rep ( i , 1 , 4 ) { can[i] = rint () ; sum += can[i] ; } if ( sum & 1 ) return puts ("NO") , 0 ; rep ( i , 1 , 4 ) if ( can[i] == sum - can[i] ) return puts ("YES") , 0 ; rep ( i , 1 , 4 ) rep ( j , i + 1 , 4 ) if ( check ( i , j ) ) return puts ("YES") , 0 ; puts ("NO") ; return 0 ; }

[CodeForces1230B][]  
题目并不难,直接贪心显然是对的.  
肯定是从高位向低位贪心.  
因为题目限制不能有前导零,所以首位不能填\\(0\\),只能填\\(1\\).后面的全赋为\\(0\\)即可.  
只需要注意,不能有前导零,也就是首位不能填\\(0\\),已经是\\(0\\)的位置不需要耗费修改次数.

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define one first #define two second #define rint read<int> #define int long long #define pb push_back #define db double using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 2e5 + 100 ; int n , k ; char s[N] ; char ans[N] ; signed main (int argc , char * argv[]) { n = rint () ; k = rint () ; scanf ("%s" , s + 1 ) ; if ( n == 1 ) { if ( k ) puts ("0") ; else putchar ( s[1] ) ; return 0 ; } int now = 2 ; ans[1] = s[1] ; if ( k && s[1] != '1' ) { ans[1] = '1' , -- k ; } while ( s[now] == '0' && now <= n ) { ans[now] = s[now] ; ++ now ; } for (int i = now ; k && i <= n ; ++ i) { ans[i] = '0' ; ++ now ; if ( s[i] != '0' ) -- k ; } rep ( i , now , n ) ans[i] = s[i] ; rep ( i , 1 , n ) putchar ( ans[i] ) ; return 0 ; }

[CodeForce1230C][]  
比较吓人的一道题.直接做没有什么好的思路.  
但数据范围比较小,所以可以直接\\(brute\\).  
采用深搜即可.枚举对着每个点的骨牌的点数应该是多少.  
对骨牌开一个\\(bool\\)标记是否用过,能放就放.  
这里有一个小技巧,深搜可以不用传统的递归写法.  
可以采用\\(STL\\)的\\(next\\\_permutation\\)函数生成对着节点的骨牌点数的全排列,注意最大点数为\\(6\\)即可.  
生成全排列后就可以直接\\(\\Theta(n^2)\\)去统计该状态的答案.取\\(max\\)即可.

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define one first #define two second #define rint read<int> #define int long long #define pb push_back #define db double using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 5e5 + 100 ; int n , m , ans = - 1 , col[N] ; bool vis[10][10] , G[10][10] ; inline int get_it () { int res = 0 ; MEM ( vis , 0 ) ; rep ( i , 1 , n ) rep ( j , 1 , n ) if ( G[i][j] ) { int u = col[i] , v = col[j] ; if ( ! vis[u][v] && ! vis[v][u] ) ++ res , vis[u][v] = vis[v][u] = true ; } return res ; } signed main (int argc , char * argv[]) { n = rint () ; m = rint () ; rep ( i , 1 , m ) { int u = rint () , v = rint () ; G[u][v] = G[v][u] = true ; } rep ( i , 1 , n ) col[i] = i ; col[7] = 6 ; do { ans = max ( ans , get_it () ) ; } while ( std::next_permutation ( col + 1 , col + n + 1 ) ) ; printf ("%lld\n" , ans ) ; return 0 ; }

[CodeForce1230D][]  
首先,显然每个学生如果在答案集合中,则必定存在另一个学生掌握他所掌握的所有技能.  
其次,如果有若干个学生的技能树相同那么他们一定可以同时存在,且缺少其中的某一个学生一定会使答案变劣.  
因为所有学生的能力值均为非负整数.  
假设我们已经把所有技能树相同的学生都放在了一起,这一定是个合法的答案.  
然后我们考虑一个学生\\(i\\),如果\\(i\\)的技能树是已经在答案中的任意一个学生的真子集(一定是真子集,因为相等都已经在答案里了),那么他就可以安全地进入答案集合中.  
否则,要么只选这个学生\\(i\\),要么取原集合,取\\(max\\)即可.

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define one first #define two second #define rint read<int> #define int long long #define pb push_back #define db double using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; using std::map ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 5e5 + 100 ; int n , ans ; pii s[N] ; map < int , int > cnt ; set < int > v ; signed main (int argc , char * argv[]) { n = rint () ; rep ( i , 1 , n ) { s[i].one = rint () ; ++ cnt[s[i].one] ; } rep ( i , 1 , n ) s[i].two = rint () ; for (map < int , int > :: iterator it = cnt.begin () ; it != cnt.end () ; ++ it) { if ( it->two <= 1 ) continue ; rep ( i , 1 , n ) if ( ( s[i].one | it->one ) == it->one ) v.insert ( i ) ; } for (set < int > :: iterator it = v.begin () ; it != v.end () ; ++ it) ans += s[*it].two ; printf ("%lld\n" , ans ) ; return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11595732.html

[CodeForces1230A]: https://codeforces.com/contest/1230/problem/A
[CodeForces1230B]: https://codeforces.com/contest/1230/problem/B
[CodeForce1230C]: https://codeforces.com/contest/1230/problem/C
[CodeForce1230D]: https://codeforces.com/contest/1230/problem/D