AtCoder Beginner Contest 155
A：签到失败，WA一次。
int main() {
int a, b, c;
cin >> a >> b >> c;
if(a == b && b == c) cout << "No";
else if(a == b || a == c || b == c) cout << "Yes";
else cout << "No";
return 0;
}
B：签到失败乘2，这题又WA一次。
int main() {
int n; scanf("%d", &n); bool ok = 1;
while(n --) {
int x; scanf("%d", &x);
if(x % 2 == 0 && (x % 3 != 0 && x % 5 != 0)) {
ok = 0;
}
}
puts(ok ? "APPROVED" : "DENIED");
return 0;
}
C：直接开map。
string s[200010];
vector<string> vec;
map<string, int> Map;
int main() {
int n; scanf("%d", &n); int ans = 0;
for(int i = 1; i <= n; i ++) {
cin >> s[i];
ans = max(ans, ++ Map[s[i]]);
}
for(int i = 1; i <= n; i ++) {
if(Map[s[i]] == ans) {
Map[s[i]] = 0;
vec.pb(s[i]);
}
}
sort(vec.begin(), vec.end());
for(auto s : vec) printf("%s
", s.c_str());
return 0;
}
D：二分 + two-pointer，正负要讨论，注意不要使用实数运算求floor和ceil。代码非常丑。
const int N = 2e5 + 10;
int n, rpos, a[N]; ll k;
ll C(ll n) { return n * (n - 1) / 2; }
ll fl(ll a, ll b) {
bool f = (a < 0) ^ (b < 0);
if(a < 0) a = -a;
if(b < 0) b = -b;
return f ? - ( a / b + 1 ) : a / b;
}
ll cl(ll a, ll b) {
bool f = (a < 0) ^ (b < 0);
if(a < 0) a = -a;
if(b < 0) b = -b;
return f ? - ( a / b ) : (a + b - 1) / b;
}
int main() {
scanf("%d%lld", &n, &k);
for(int i = 1; i <= n; i ++) scanf("%d", a + i);
sort(a + 1, a + n + 1);
ll l = 0, r = 0, z = 0, L = 0, R = 0, Z = 0;
for(int i = 1; i <= n; i ++) z += a[i] == 0;
for(int i = 1; i <= n; i ++) l += a[i] < 0;
for(int i = 1; i <= n; i ++) r += a[i] > 0;
L = l * r; R = C(l) + C(r); Z = C(n) - L - R;
rpos = n + 1;
for(int i = 1; i <= n; i ++) if(a[i] > 0) {
rpos = i; break ;
}
if(k <= L) {
ll ql = -1e18, qr = -1, mid, ans = -233;
while(ql <= qr) {
mid = (ql + qr) >> 1;
ll sum = 0, now = r, cur = rpos;
for(int i = 1; i <= n && a[i] < 0; i ++) {
ll up = mid % a[i] == 0 ? mid / a[i] + 1 : cl(mid, a[i]);
while(now && a[cur] < up) cur ++, now --;
sum += now;
}
if(sum < k) ql = (ans = mid) + 1;
else qr = mid - 1;
}
printf("%lld
", ans);
} else if(k <= L + Z) {
puts("0");
} else {
k -= L + Z;
ll ql = 1, qr = 1e18, mid, ans = -233;
while(ql <= qr) {
mid = (ql + qr) >> 1;
ll sum = 0, now = r, cur = n;
for(int i = rpos; i <= n; i ++) {
ll up = mid % a[i] == 0 ? mid / a[i] - 1 : fl(mid, a[i]);
while(now && a[cur] > up) cur --, now --;
sum += cur >= i ? now - 1 : now;
}
now = l; cur = 1;
for(int i = n; i >= 1; i --) if(a[i] < 0) {
ll up = mid % a[i] == 0 ? mid / a[i] + 1 : cl(mid, a[i]);
while(now && a[cur] < up) cur ++, now --;
sum += cur <= i ? now - 1 : now;
}
sum >>= 1;
if(sum < k) ql = (ans = mid) + 1;
else qr = mid - 1;
}
printf("%lld
", ans);
}
return 0;
}
E：dp[i][0/1]表示前i位，第i位要不要借给下一位，最小代价。
char s[N];
int dp[N][2];
bool ok(int x) { return x >= 0 && x < 10; }
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
dp[0][1] = 1; dp[0][0] = 0;
for(int i = 1; i <= n; i ++) {
dp[i][0] = dp[i][1] = 1e9;
int x = s[i] - '0';
for(int j = 0; j < 10; j ++) {
if(ok(10 + j - x)) dp[i][0] = min(dp[i][0], dp[i - 1][1] + j + (10 + j - x));
if(ok(j - x)) dp[i][0] = min(dp[i][0], dp[i - 1][0] + j + (j - x));
if(ok(10 + (j - 1) - x)) dp[i][1] = min(dp[i][1], dp[i - 1][1] + j + (10 + j - 1 - x));
if(ok(j - 1 - x)) dp[i][1] = min(dp[i][1], dp[i - 1][0] + j + (j - 1 - x));
}
}
printf("%d
", dp[n][0]);
return 0;
}
F：差分，然后区间xor变成两点同时xor。所有l和r+1连边建图，问题转换为选若干条边，一条边被选两个端点就xor上1。
对于每个连通块dfs，如果当前子树的根状态为1就选这条边，否则不选，这样若不合法只可能根不合法。若根不合法，显然无解，因为若要选非dfs树边，一定会出现其他不合法点。
const int N = 2e5 + 10;
struct node {
int a, b;
} x[N], t[N];
int n, q, b[N];
bool ans[N], st[N], vis[N];
vector<pii> G[N];
int get(int u) { return lower_bound(b + 1, b + n + 1, u) - b; }
int getl(int u) { return upper_bound(b + 1, b + n + 1, u) - b - 1; }
void link(int u, int v, int w) { G[u].pb(pii(v, w)); G[v].pb(pii(u, w)); }
int dfs(int u) {
vis[u] = 1; int x = st[u];
for(auto v : G[u]) if(!vis[v.fs]) {
if(dfs(v.fs)) { ans[v.sc] = 1; x ^= 1; }
}
return x;
}
int main() {
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; i ++) { scanf("%d%d", &x[i].a, &x[i].b); b[i] = x[i].a; }
for(int i = 1; i <= q; i ++) scanf("%d%d", &t[i].a, &t[i].b);
sort(b + 1, b + n + 1);
for(int i = 1; i <= n; i ++) { x[i].a = get(x[i].a); st[x[i].a] = x[i].b; }
for(int i = n + 1; i >= 1; i --) st[i] ^= st[i - 1];
for(int i = 1; i <= q; i ++) link(get(t[i].a), 1 + getl(t[i].b), i);
for(int i = 1; i <= n + 1; i ++) if(!vis[i]) {
if(dfs(i)) { puts("-1"); return 0; }
}
int r = 0;
for(int i = 1; i <= q; i ++) r += ans[i];
printf("%d
", r);
for(int i = 1; i <= q; i ++) if(ans[i]) printf("%d ", i);
return 0;
}