A Discount
int main()
{
IOS;
int a, b;
cin >> a >> b;
cout << setprecision(10) << (double)(a - b) / a * 100 << endl;
return 0;
}
B Play Snuke
int main()
{
int n;
scanf("%d", &n);
int res = INF;
for(int i = 1; i <= n; ++ i)
{
int a, p, x; scanf("%d%d%d", &a, &p, &x);
if(a < x) res = min(p, res);
}
if(res < INF) printf("%d
", res);
else puts("-1");
return 0;
}
C
(a) 只需要枚举到 (sqrt(n)), 用 set 判重即可
int main()
{
IOS;
LL n; cin >> n;
unordered_set<LL> s;
for(LL i = 2; i <= n / i; ++ i)
{
LL t = i * i;
while(t <= n) { s.insert(t); t *= i; }
}
cout << n - s.size() << endl;
return 0;
}
D Poker
枚举最后一位，判断该放置方法是否合法， 此方法的方案数为 (v[i] * (v[j] - (i == j)))
总方案数为 ((9 * k - 8) * (9 * k - 9))
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
LL score(string s)
{
vector<LL> v(10);
iota(v.begin(), v.end(), 0);
for(auto c : s)
v[(int)(c - '0')] *= 10;
return accumulate(v.begin(), v.end(), 0);
}
int main()
{
IOS;
LL k;
string a, b;
cin >> k >> a >> b;
vector<LL> v(10, k);
for(auto c : a + b) v[(int)(c - '0')] --;
LL res = 0;
for(LL i = 1; i <= 9; ++ i)
for(LL j = 1; j <= 9; ++ j)
{
a.back() = '0' + i;
b.back() = '0' + j;
if(score(a) <= score(b)) continue;
else res += v[i] * (v[j] - (i == j));
}
cout << setprecision(10) << (double)res / (9 * k - 8) / (9 * k - 9) << endl;
return 0;
}
E Oversleeping
求满足 (X le t ; mod (2X + 2Y) < X + Y) 且 (P le t ; mod (P + Q) < P + Q) 的最小正整数 (t)
(Y) 和 (Q) 都比较小，可以直接枚举
问题转化成 (egin{cases}t equiv m_1 (mod;a_1)\t equiv m_2(mod;a_2)end{cases}), 用扩展中国剩余定理求解即可.
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if(!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main()
{
IOS;
LL X, Y, P, Q;
int __;
cin >> __;
while(__ -- )
{
cin >> X >> Y >> P >> Q;
LL res = 2e18;
for(int i = 0; i < Y; ++ i)
for(int j = 0; j < Q; ++ j)
{
LL a1 = 2 * X + 2 * Y, a2 = P + Q;
LL m1 = X + i, m2 = P + j;
LL k1, k2;
LL d = exgcd(a1, a2, k1, k2);
if((m2 - m1) % d) continue;
k1 *= (m2 - m1) / d;
LL t = a2 / d;
k1 = (k1 % t + t) % t;
m1 = a1 * k1 + m1;
a1 = abs(a1 / d * a2);
res = min(res, (m1 % a1 + a1) % a1);
}
if(res < 2e18) cout << res << endl;
else cout << "infinity" << endl;
}
return 0;
}
F Zebraness
(i + j) 为偶数的格子和为奇数的格子形成一张二分图，考虑将 (i + j) 为奇数的格子上的颜色翻转，同色的块在翻转后变成异色，则会对答案产生贡献，那么最小化这个贡献，用总边数减掉这些反的贡献，就是在原图中贡献的最大值。
- 从虚拟源点向新图上为白色的点连一条容量为 (+infty) 的边，确保这条边不会被选成割边
- 从新图上为黑色的点向虚拟汇点连一条容量为 (+infty) 的边，确保这条边不会被选成割边
- 相邻的点之间连正反两条容量为 (1) 的边，这些边可以被选作割边
答案即为 (2 * n * (n - 1)) - 最小割
#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 10;
const int M = (10000 + 100 * 100 * 4 + 10) * 2;
const int INF = 1e9;
int n, S, T;
struct Edge
{
int to, nxt, flow;
}line[M];
int fist[N], idx;
int d[N], cur[N];
char str[110];
int get(int x, int y)
{
return n * (x - 1) + y;
}
void add(int x, int y, int z1, int z2)
{
line[idx] = {y, fist[x], z1};
fist[x] = idx ++;
line[idx] = {x, fist[y], z2};
fist[y] = idx ++;
}
bool bfs()
{
queue<int> q;
memset(d, -1, sizeof d);
q.push(S), d[S] = 0, cur[S] = fist[S];
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = fist[u]; ~i; i = line[i].nxt)
{
int v = line[i].to;
if(d[v] == -1 && line[i].flow)
{
d[v] = d[u] + 1;
cur[v] = fist[v];
if(v == T) return 1;
q.push(v);
}
}
}
return 0;
}
int find(int u, int limit)
{
if(u == T) return limit;
int flow = 0;
for(int i = cur[u]; i != -1 && flow < limit; i = line[i].nxt)
{
cur[u] = i;
int v = line[i].to;
if(d[v] == d[u] + 1 && line[i].flow)
{
int t = find(v, min(line[i].flow, limit - flow));
if(!t) d[v] = -1;
line[i].flow -= t;
line[i ^ 1].flow += t;
flow += t;
}
}
return flow;
}
int dinic()
{
int res = 0, flow;
while(bfs()) while(flow = find(S, INF)) res += flow;
return res;
}
int main()
{
scanf("%d", &n);
memset(fist, -1, sizeof fist);
S = 0, T = n * n + 1;
for(int i = 1; i <= n; ++ i)
{
scanf("%s", str + 1);
for(int j = 1; j <= n; ++ j)
{
if(str[j] == '?') continue;
if((i + j) & 1) str[j] = (str[j] == 'B') ? 'W' : 'B';
if(str[j] == 'W') add(S, get(i, j), INF, 0);
if(str[j] == 'B') add(get(i, j), T, INF, 0);
}
}
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
{
if(j + 1 <= n) add(get(i, j), get(i, j + 1), 1, 1);
if(i + 1 <= n) add(get(i, j), get(i + 1, j), 1, 1);
}
printf("%d
", 2 * n * (n - 1) - dinic());
return 0;
}