A题：给你n个数，让你找出里面最大的数字，并把其他数字补到最大的数值，问需要补多少。直接两遍for就行了。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <string> #include <stack> #include <map> #include <set> #include <bitset> #define X first #define Y second #define clr(u,v); memset(u,v,sizeof(u)); #define in() freopen("data","r",stdin); #define out() freopen("ans","w",stdout); #define Clear(Q); while (!Q.empty()) Q.pop(); #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 10; const int INF = 0x3f3f3f3f; int N[maxn]; int main() { int n; scanf("%d", &n); int Max = -INF; for (int i = 0; i < n; i++) { cin >> N[i]; Max = max(Max, N[i]); } ll ans = 0; for (int i = 0; i < n; i++) ans += Max - N[i]; cout << ans << endl; return 0; }
B题：给你一个字符串，包含RBYG!五种字符，其中!字符可以修改为任意字符，同时，字符串按照abcdabcd……这样的格式，abcd分别为RBYG中的任意一个，且互不相同。现在问你要分别把!改成哪些字符才能使原字符串合法，输出需要多少个RBYG。我们只要考虑前四位就行了，dfs出前四位的所有情况，然后判断是不是合法。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <string> #include <stack> #include <map> #include <set> #include <bitset> #define X first #define Y second #define clr(u,v); memset(u,v,sizeof(u)); #define in() freopen("data","r",stdin); #define out() freopen("ans","w",stdout); #define Clear(Q); while (!Q.empty()) Q.pop(); #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 10; const int INF = 0x3f3f3f3f; char str[210]; int R = 0, B = 0, Y = 0, G = 0; int N[100]; const char s[] = {"RBYG"}; bool ok(int cur, int n) { for (int i = 0; i < cur; i++) if (str[i] == str[cur]) return 0; for (int i = cur + 4; i < n; i += 4) if (str[i] != '!' && str[cur] != str[i]) return 0; for (int i = cur + 4; i < n; i += 4) if (str[i] == '!') N[str[cur]]++; return 1; } void dfs(int cur , int n, int len) { if (cur == n) return ; if (str[cur] == '!') { for (int i = 0; i < 4; i++) { str[cur] = s[i]; if (ok(cur, len)) { N[s[i]]++; dfs(cur + 1, n, len); return ; } } } else ok(cur, len); dfs(cur + 1, n, len); } int main() { scanf("%s", str); int len = strlen(str); dfs(0, 4, len); for (int i = 0; i < 4; i++) cout << N[s[i]] << " "; return 0; }
C题：有n*m个学生，老师有k个问题，按照行:1~n~1,列1~m的顺序提问。然后给你Sergei的坐标，让你输出班上被问问题最多的次数，最少的次数以及Sergei被问了多少次。由于n和m不大，可以借助数组来模拟一下（不用数组的话细节很多）。可以考虑，(2n-1)*m是一个周期，所以直接模拟k%((2n-1)*m)这一部分就行了，复杂度不会很高，当然要注意特判n==1的情况。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <string> #include <stack> #include <map> #include <set> #include <bitset> #define X first #define Y second #define clr(u,v); memset(u,v,sizeof(u)); #define in() freopen("data","r",stdin); #define out() freopen("ans","w",stdout); #define Clear(Q); while (!Q.empty()) Q.pop(); #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 10; const int INF = 0x3f3f3f3f; const ll inf = 1e18 + 10; ll M[210][210]; int main() { ll n, m, k; ll x, y; cin >> n >> m >> k >> x >> y; if (n == 1) { ll add = k / m, mod = k % m; for (int j = 1; j <= m; j++) M[1][j] += add; for (int j = 1; j <= m && mod; j++) { M[1][j]++; mod--; } } else { ll add = k / ((2 * n - 2) * m); for (int i = 2; i < n; i++) for (int j = 1; j <= m; j++) M[i][j] += 2 * add; for (int j = 1; j <= m; j++) M[n][j] += add; for (int j = 1; j <= m; j++) M[1][j] += add; ll mod = k % ((2 * n - 2) * m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (mod) { M[i][j]++; mod--; } else break; for (int i = n - 1; i > 1; i--) for (int j = 1; j <= m; j++) if (mod) { M[i][j]++; mod--; } else break; } ll ans = M[x][y] ; ll Min = inf, Max = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (M[i][j] != -1) { Min = min(Min, M[i][j]); Max = max(Max, M[i][j]); } } cout << Max << " " << Min << " " << ans; return 0; }
D题：给你一个n进制的数字k，让你把它转为十进制，且这个数字ans要最小。因为会出现数字k中的两位或者多位组合成ans中的一位，所以ans不是唯一的。可以考虑贪心，从后面取数字，经可能取大的数字。大概证明：假设数字为ab，为c进制，那么有a<c,b<c,假设ab<c,那么ab*c<c*c<a*c*c+b*c，这就说明如果能选多位，尽可能选多位。这题细节很多，最麻烦的就是0的问题了，细节自己搞定吧。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <string> #include <stack> #include <map> #include <set> #include <bitset> #define X first #define Y second #define clr(u,v); memset(u,v,sizeof(u)); #define in() freopen("data","r",stdin); #define out() freopen("ans","w",stdout); #define Clear(Q); while (!Q.empty()) Q.pop(); #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 10; const int INF = 0x3f3f3f3f; char str[maxn]; ll pow(ll n, ll k) { ll ans = 1; while (k > 0) { if (k & 1) ans *= n; k >>= 1; n = n * n; } return ans; } int main() { ll n, ans = 0; cin >> n; cin >> (str + 1); int len = strlen(str + 1); ll k = 0; str[0] = '0'; int pre = len; for (int i = len; i >= 0; i--) { int pos = i; ll num = 0; while (pos <= pre && num < n) { num *= 10; num += str[pos] - '0'; pos++; } if (num >= n || i == 0) { pos = i + 1; num = 0; int flag = 0; while (str[pos] == '0') { pos++; flag = 1; } int temp = pos - 1; while (pos <= pre) { num *= 10; num += str[pos] - '0'; pos++; } if (num == 0 && str[pre] == '0') { str[pre] = ' '; k++; i++; pre--; continue; } if (flag) i++; ans += num * pow(n, k); k++; pre = temp; } } cout << ans << endl; return 0; }
因为有事，这场是后来补的题，不过还是开了Virtual participation模拟一下，只做了三题。B题卡的时间有点久，可能太久没处理递归了，写得头脑发热，调试了半天。A和C题比较容易，D题比较容易想出贪心，但是细节很多，后来再补题也是卡了很久。。感觉自己处理细节能力下降了，得多练习模拟题。
2017-01-21 01:43:08