A Large Digits
int n;
int main()
{
IOS;
int a, b, resa = 0, resb = 0;
cin >> a >> b;
while(a) resa += a % 10, a /= 10;
while(b) resb += b % 10, b /= 10;
cout << max(resa, resb) << endl;
return 0;
}
B Gentle Pairs
int n;
int x[N], y[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) scanf("%d%d", &x[i], &y[i]);
int res = 0;
for(int i = 1; i <= n; ++ i)
for(int j = i + 1; j <= n; ++ j)
{
if(x[i] - x[j] == 0) continue;
if(x[i] - x[j] > 0)
{
if(y[i] - y[j] >= x[j] - x[i] && y[i] - y[j] <= x[i] - x[j])
res ++;
}
if(x[i] - x[j] < 0)
{
if(y[i] - y[j] <= x[j] - x[i] && y[i] - y[j] >= x[i] - x[j])
res ++;
}
}
printf("%d
", res);
}
C 1-SAT
int n;
map mp;
string str;
int main()
{
IOS;
cin >> n;
for(int i = 1; i <= n; ++ i)
{
cin >> str;
if(str[0] == '!' && mp.count(str.substr(1)))
{
cout << str.substr(1) << endl;
return 0;
}
if(str[0] != '!' && mp.count("!" + str))
{
cout << str << endl;
return 0;
}
mp[str] = 1;
}
puts("satisfiable");
return 0;
}
D Choose Me
不选时(A += a_i), (B += 0), 选时 (A += 0), (B += a_i + b_i)
先考虑都不选，每选择一个相当于从(A)中减去一个(a_i)，(B)加一个(a_i + b_i)，因为是比较大小关系，所以等价于(A)不动，(B + 2 imes a_i + b_i)
int n;
struct zt
{
int a, b;
LL c;
}t[N];
bool cmp(zt a, zt b)
{
return a.c > b.c;
}
int main()
{
scanf("%d", &n);
LL sum = 0, res = 0;
for(int i = 1; i <= n; ++ i)
{
scanf("%d%d", &t[i].a, &t[i].b);
t[i].c = t[i].a * 2 + t[i].b;
sum += t[i].a;
}
sort(t + 1, t + n + 1, cmp);
for(int i = 1; i <= n; ++ i)
{
res += t[i].c;
if(res > sum) { printf("%d
", i); break;}
}
return 0;
}
E Through Path
树上差分
以1号点为根，预处理每个点的深度.
若对于深度大的点所在分支（即它的子树）全部(+x),只需要对该点(+x).
若对于深度小的点所在分支全部(+x)，可以看成所有点(+x),深度大的点所在子树(-x)，故维护一个所有点的增加值，并对深度大的点(-x).
最后遍历一遍子树把标记下传即可.
int n, m;
struct Edge
{
int to, nxt;
}line[N * 2];
int fist[N], idx;
int dep[N];
LL d[N], res;
void add(int x, int y)
{
line[++ idx] = (Edge){y, fist[x]};
fist[x] = idx;
}
void dfs(int u, int far)
{
for(int i = fist[u]; i != -1; i = line[i].nxt)
{
int v = line[i].to;
if(v == far) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
void dfs2(int u, int far)
{
for(int i = fist[u]; i != -1; i = line[i].nxt)
{
int v = line[i].to;
if(v == far) continue;
d[v] += d[u];
dfs2(v, u);
}
}
int main()
{
memset(fist, -1, sizeof fist);
scanf("%d", &n);
for(int i = 1; i < n; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
dfs(1, -1);
scanf("%d", &m);
for(int i = 1; i <= m; ++ i)
{
int t, e, x;
scanf("%d%d%d", &t, &e, &x);
int a = line[2 * e].to, b = line[2 * e - 1].to;
if(dep[a] < dep[b] && t == 2) d[b] += x;
if(dep[a] > dep[b] && t == 1) d[a] += x;
if(dep[a] < dep[b] && t == 1) { d[b] -= x; res += x; }
if(dep[a] > dep[b] && t == 2) { d[a] -= x; res += x; }
}
dfs2(1, -1);
for(int i = 1; i <= n; ++ i) printf("%lld
", d[i] + res);
return 0;
}
F Close Group
令f[i]表示状态i划分的团的个数集合中的最小值.
枚举i的子集s， f[i] = min(f[i], f[i - s] + f[s])
int n, m;
int conn[1 << N];
int f[1 << N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
a -- , b -- ;
conn[a] |= (1 << b);
conn[b] |= (1 << a);
}
for(int i = 0; i < n; ++ i) conn[i] |= (1 << i);
memset(f, 0x3f, sizeof f);
f[0] = 0;
for(int i = 1; i < (1 << n); ++ i)
{
int flag = 1;
for(int j = 0; j < n; ++ j)
if(i & (1 << j) && (conn[j] & i) != i)
{
flag = 0;
break;
}
if(flag) f[i] = 1;
for(int s = i; s; s = (s - 1) & i)
f[i] = min(f[i], f[i - s] + f[s]);
}
printf("%d
", f[(1 << n) - 1]);
return 0;
}
2021.1.21