A
#include <cstdio> #include <cstring> #include <cmath> #include <sstream> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define pill pair<int, int> #define mk make_pair #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i < n; ++i) const int qq = 1e5 + 10; int n, m, k; int num[qq]; int main(){ int l, r; scanf("%d%d", &l, &r); if(l == r){ printf("%d\n", l); return 0; } printf("2\n"); return 0; }
B #include <cstdio> #include <cstring> #include <cmath> #include <sstream> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define pill pair<int, int> #define mk make_pair #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i < n; ++i) const int qq = 1e5 + 10; int n, m, k; int num[qq]; int main(){ scanf("%d", &n); int t = 0; for(int i = 1; i <= n; ++i){ if(t == 0) putchar('a'); if(t == 1) putchar('a'); if(t == 2) putchar('b'); if(t == 3) putchar('b'); t++; if(t == 4) t = 0; } puts(""); return 0; } C #include <cstdio> #include <cstring> #include <cmath> #include <sstream> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define pill pair<int, int> #define mk make_pair #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i < n; ++i) const int qq = 1e5 + 10; int n, m, k; int num[qq]; int main(){ scanf("%d", &n); if(n == 1 || n == 2){ printf("0\n"); return 0; } printf("%d\n", (n - 1) / 2); return 0; } D
题意：ab能变成bba，询问最多可以操作多少次。
思路：从结果来看我们知道最后一定是bbbb....aaa....，可知其实操作就是将所有的a向右边移动，要使得操作次数最多我们可以从最右端的a开始向右端挪动，每次将一个a移动到不能再移动，此时b的数量变成原来的两倍。然后模拟即可
#include <cstdio> #include <cstring> #include <cmath> #include <sstream> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define pill pair<int, int> #define mk make_pair #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i < n; ++i) const int qq = 1e6 + 10; const int mod = 1e9 + 7; int n, m, k; char st[qq]; int main(){ scanf("%s", st); LL ans = 0; LL b = 0; int len = (int)strlen(st) - 1; for(int i = len; i >= 0; --i){ if(b == 0 && st[i] == 'a') continue; if(st[i] == 'b') b = (b + 1) % mod; else if(st[i] == 'a') ans = (ans + b + mod) % mod, b = (2ll * b + mod) % mod; } printf("%lld\n",(ans + mod) % mod); return 0; }E
题意：有n个节点，每一个节点上有si个ice cream，现在要让ice cream组成一个图G， ice cream中任意两个点存在边的条件是属于同一个节点(n中的节点)，换句话说也就是每一个节点上的点都组成一个完全图，现在问你最小染色数以及方案
思路：我一直以为后面给的树是完全没有用的，恩。。。 其实是漏了这么一句话
Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph
就是拥有 i-th (1 ≤ i ≤ m) type of ice cream的节点组成一个连通图，k个节点，k - 1条边的连通图。
如果我们对每一个节点去进行染色的话， 从1开始递进染色，这里会有很多意想不到的情况，具体可以自己试试然后看看自己错的那组数据，所以题目这么说就是为了把我们的思路转向所给的树上，对树来进行dfs染色。
#include <bits/stdc++.h> using namespace std; #define LL long long #define pb push_back #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i < n; ++) const int qq = 5e5 + 10; vector<int> T[qq], G[qq]; map<int, bool> mp; int color[qq]; int maxn = 1; void Dfs(int u, int fa){ mp.clear(); for(int v : G[u]){ if(color[v]) mp[color[v]] = true; } int cnt = 1; for(int v : G[u]){ if(!color[v]){ while(mp[cnt] == true) cnt++; mp[cnt] = true; color[v] = cnt; } } maxn = max(maxn, cnt); for(int v : T[u]){ if(v == fa) continue; Dfs(v, u); } } int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i){ int k; scanf("%d", &k); for(int j = 0; j < k; ++j){ int x; scanf("%d", &x); G[i].pb(x); } } int a, b; for(int i = 1; i < n; ++i){ scanf("%d%d", &a, &b); T[a].pb(b), T[b].pb(a); } Dfs(1, 0); for(int i = 1; i <= m; ++i) if(!color[i]) color[i] = 1; printf("%d\n", maxn); for(int i = 1; i <= m; ++i){ printf("%d ", color[i]); } puts(""); return 0; }
