首页 > 代码库 > Codeforces Round #260 (Div. 2) ABCDE
Codeforces Round #260 (Div. 2) ABCDE
A题逗比了，没有看到All ai are distinct. All bi are distinct. 其实很水的。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 #define mnx 100002 8 9 10 struct latop{11 int p, q;12 bool operator < ( const latop & b ) const {13 return p < b.p;14 }15 }a[mnx];16 int main(){17 int n;18 scanf( "%d", &n );19 for( int i = 0; i < n; i++ ){20 scanf( "%d %d", &a[i].p, &a[i].q );21 }22 sort( a, a + n );23 bool flag = 0;24 for( int i = 1; i < n; i++ ){25 if( a[i].q < a[i-1].q ) flag = 1;26 }27 if( flag ) puts( "Happy Alex" );28 else puts( "Poor Alex" );29 return 0;30 }
B题找循环节。。循环节是4，然后输入再长的数，也只需要看最后两位，因为100的倍数肯定能够整除4，就看最后两位。。结果又逗比了，数组开小了，最后re了。。太粗心了。。
1 #include<string> 2 #include<cmath> 3 #include<map> 4 #include<queue> 5 6 using namespace std; 7 8 #define mnx 1000000 9 #define PI acos(-1.0)10 #define ll long long11 #define ull unsigned long long12 #define inf 0x3f3f3f3f13 #define eps 1e-814 #define MP make_pair15 #define lson l, m, rt << 116 #define rson m+1, r, rt << 1 | 117 #define mod 233333318 19 int a[4] = { 4, 0, 0, 0 };20 char ch[mnx];21 int main(){22 scanf( "%s", &ch );23 int n = strlen( ch );24 int k = 0;25 if( n <= 2 ){26 for( int i = 0; i < n; i++ ){27 k = k * 10 + ch[i] - ‘0‘;28 }29 // cout<<k<<endl;30 k %= 4;31 printf( "%d\n", a[k] );32 }33 else{34 for( int i = n-2; i < n; i++ ){35 k = k * 10 + ch[i] - ‘0‘;36 }37 // cout<<k<<endl;38 k %= 4;39 printf( "%d\n", a[k] );40 }41 return 0;42 }
C题先排序，然后把相同的弄掉，if( b[i] == b[i-1] + 1 ) dp[i] = max( dp[i-2] + sum[i], dp[i-1] ),要么就是选当前这个b[i],然后dp[i]的值就是dp[i-2] + sum[i],要么就选b[i-1]，然后dp[i]的值就是dp[i-1]；else dp[i] = dp[i] = dp[i-1] + sum[i]; 最后答案就是 dp[cnt]; 具体看代码。。当时写的比较稳妥，多写了一些。。结果还是因为longlong跪了几发，这是后来写的代码
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<string> 6 #include<cmath> 7 #include<map> 8 #include<queue> 9 10 using namespace std;11 12 #define mnx 20000013 #define PI acos(-1.0)14 #define ll long long15 #define ull unsigned long long16 #define inf 0x3f3f3f3f17 #define eps 1e-818 #define MP make_pair19 #define lson l, m, rt << 120 #define rson m+1, r, rt << 1 | 121 #define mod 233333322 23 ll a[mnx], b[mnx], sum[mnx], dp[mnx];24 int main(){25 int n;26 scanf( "%d", &n );27 for( int i = 1; i <= n; i++ ){28 scanf( "%I64d", &a[i] );29 }30 sort( a + 1, a + 1 + n );31 int cnt = 0;32 for( int i = 1; i <= n; i++ ){33 if( a[i] != b[cnt] ){34 ++cnt;35 b[cnt] = a[i];36 sum[cnt] = a[i];37 }38 else sum[cnt] += a[i];39 }40 dp[1] = sum[1]; 41 for( int i = 2; i <= cnt; i++ ){42 if( b[i] == b[i-1] + 1 ){43 dp[i] = max( dp[i-2] + sum[i], dp[i-1] );44 }45 else{46 dp[i] = dp[i-1] + sum[i];47 } 48 }49 cout<<dp[cnt]<<endl;50 return 0;51 }
D题trie树，不会做。。赛后问了思路，弄了很久才明白。。原本的想法是 trie的根就是必败，然后dfs，第一层就是必胜，遍历到叶子节点，看叶子节点是必败还是必胜，如果叶子节点全是必胜的，说明先手的每次必胜，如果叶子节点全是必败的，说明先手的每次必败,如果叶子节点既有必胜又有必败的，说明先手的每次既能必胜也能必败。。后来发现这样想是错的，如果是abcs，abcab，先手走到c，接下来先手的输赢全部是由后手决定，后手走s，先手输，后手走a，先手赢。。这道题输赢的状态必须由叶子节点开始向根的方向推，看了超哥的代码，开两个bool数组，win[], can[],win数组表示下一步先手开始走，能不能赢，can数组表示下一步先手开始走，能不能输。。所以叶子节点就是win[u] = 0(先手下一步不能走，就不能赢)，can[u] = 1(先手下一步不能走，肯定输)。。当一个节点有多个子节点，win[u] = 1就看 win[son[u][i]]里面有没有为0的，否则就是0；can[u] = 1就看can[son[u][i]]里面有没有为0的，否则就是0。。推到根节点的状态。。这样讲有点抽象，可以手动模拟一下 abcs， abcab这种情况。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 #define mnx 100002 8 9 int son[mnx][26], tot;10 bool win[mnx], can[mnx];11 void insert(char *s) {12 int t = 0;13 for (int i = 0; s[i]; ++i) {14 int c = s[i] - ‘a‘;15 if (!son[t][c]) son[t][c] = ++tot;16 t = son[t][c];17 }18 }19 void dfs( int u ){20 win[u] = 0, can[u] = 1;21 bool hav = 0;22 for( int i = 0; i < 26; i++ ){23 if( son[u][i] ){24 dfs( son[u][i] ); hav = 1;25 }26 }27 if( !hav ) return ;28 can[u] = 0;29 for( int i = 0; i < 26; i++ ){30 if( son[u][i] && !win[son[u][i]] ) win[u] = 1;31 if( son[u][i] && !can[son[u][i]] ) can[u] = 1;32 }33 }34 char ch[mnx];35 int main(){36 int n, k;37 scanf( "%d%d", &n, &k );38 for( int i = 0; i < n; i++ ){39 scanf( "%s", ch );40 insert( ch );41 }42 dfs( 0 );43 if( win[0] == false ) puts( "Second" );44 else{45 if( can[0] == true ) puts( "First" );46 else puts( (k & 1) ? "First" : "Second" );47 }48 return 0;49 }
E题没时间看，赛后看了一下，发现也不是很难，树的直径和并查集。。比较难处理的就是connect them by a road so as to minimize the length of the longest path in the resulting region 使联通后的区域的直径最小，那么就应该从两条直径的中间点连一条边，使他们联通。。假设要联通两个区域为u，v，直径为val[u], val[v]，则联通后的直径应该是 max( val[u], val[v], 1 + ( val[u] - val[u] / 2 ) + ( val[v] - val[v] / 2 );
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 #define mnx 600005 8 #define inf 0x3f3f3f3f 9 10 int dis[2][mnx], fa[mnx], val[mnx];11 int vv[mnx], first[mnx], nxt[mnx], e;12 bool vis[mnx], in[mnx];13 int n, m, query, tot;14 void init(){15 memset( first, -1, sizeof(first) );16 memset( dis, 0x3f, sizeof(dis) );17 e = 0;18 }19 void add( int u, int v ){20 vv[e] = v, nxt[e] = first[u], first[u] = e++;21 }22 int q[mnx];23 int bfs( int s, int *dis ){24 int head = 0, tail = 0;25 q[tail++] = s, dis[s] = 0;26 while( head < tail ){27 int u = q[head++];28 vis[u] = 1;29 for( int i = first[u]; i != -1; i = nxt[i] ){30 int v = vv[i];31 if( dis[v] > dis[u] + 1 ){32 dis[v] = dis[u] + 1;33 q[tail++] = v;34 } 35 }36 }37 int id = s, d = dis[s];38 for( int i = 0; i < tail; i++ ){39 if( dis[q[i]] > d ){40 d = dis[q[i]], id = q[i];41 }42 }43 return id;44 }45 int find( int s ){46 if( s != fa[s] ){47 fa[s] = find( fa[s] );48 }49 return fa[s];50 }51 void treeD( int s ){52 int v = bfs( s, dis[0] );53 int u = bfs( v, dis[1] );54 val[find(u)] = dis[1][u];55 }56 int main(){57 scanf( "%d %d %d", &n, &m, &query );58 tot = n;59 init();60 for( int i = 0; i <= n + query; i++ ){61 fa[i] = i;62 }63 while( m-- ){64 int u, v;65 scanf( "%d %d", &u, &v );66 add( u, v ), add( v, u );67 int fu = find( u ), fv = find( v );68 fa[fu] = fv;69 }70 for( int i = 1; i <= n; i++ ){71 if( !vis[i] ){72 treeD( i );73 }74 }75 while( query-- ){76 int tye, u, v;77 scanf( "%d", &tye );78 if( tye == 1 ){79 scanf( "%d", &u );80 printf( "%d\n", val[find(u)] );81 }82 else{83 scanf( "%d%d", &u, &v );84 int fu = find( u ), fv = find( v );85 if( fu == fv ) continue;86 ++tot;87 fa[fu] = fa[fv] = tot;88 val[tot] = 1 + ( val[fu] - val[fu] / 2 ) + ( val[fv] - val[fv] / 2 );89 val[tot] = max( val[tot], val[fu] );90 val[tot] = max( val[tot], val[fv] );91 }92 }93 return 0;94 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。