A - Gambling on Choosing Regionals
题意
\(k\)场比赛，每场比赛每个大学至多\(c_i\)个队；总\(n\)个队伍，每队有分数与所属大学两个属性，每只队伍至多参加\(2\)场比赛。求各个队在最坏情况下的最优排名。
思路
最坏情况就是你打哪场，强队都去哪场，就选\(c_i\)小的场次，能让排名更靠前。对于每队能打两场，最坏情况，两场强队都跟着你，故考虑一场即可。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct group
{
int id, sc;
string ut;
bool operator < (const group a)
{
return sc > a.sc;
}
};
void solve()
{
int n, k, minn = LLONG_MAX;
cin >> n >> k;
for (int i = 0; i < k; i++)
{
int x;
cin >> x;
minn = min(minn, x); // 人最少的场次
}
vector<group> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i].sc >> v[i].ut;
v[i].id = i;
}
sort(v.begin(), v.end()); // 按分数降序排
map<string, int> cnt;
vector<int> ans(n);
int cur = 0;
for (int i = 0; i < n; i++)
{
if (cnt[v[i].ut] < minn) // v[i]所属大学的名额还有
{
cur++;
cnt[v[i].ut]++;
}
ans[v[i].id] = cur;
}
for (int i = 0; i < n; i++)
{
cout << ans[i] << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
F - Tourist
题意
初始值\(1500\)，给\(n\)个数，相加后问能否\(\ge 4000\)，能则输出在第几次恰好\(\ge 4000\)，否则输出-\(1\)。
思路
模拟。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n, sum = 1500;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
sum += x;
if (sum >= 4000)
{
cout << i + 1 << endl;
return;
}
}
cout << -1 << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
G - Game
题意
\(A\)与\(B\)玩游戏，最初各有\(x\)。\(y\)的筹码，各自赢的概率为\(p_0\)、\(p_1\)，平局概率为\(1-p_0-p_1\)。平局时立刻进行下一局；当赢家的筹码\(\ge\)输家的，游戏结束，此时的赢家获胜；每局的输家要失去赢家此时的筹码数。问\(A\)最后获胜的概率。
思路
其实只用考虑3种情况：\(x = y\)、\(x < y\)、\(x > y\)，然后递归，加上辗转相除递归次数不会很多。除法用逆元处理。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int x, y, a, b, c, p0, p1, p2;
int qpow(int base, int x) // 快速幂
{
int res = 1;
while (x)
{
if (x & 1)
{
res *= base;
res %= mod;
}
x >>= 1;
base *= base;
base %= mod;
}
return res;
}
int dfs(int x, int y)
{
if (x == y) // 筹码一样输了就死
{
return p0;
}
if (x < y) // 筹码少，只能一直赢
{
int cnt = y / x;
if (y % x == 0)
{
cnt--; // 留一次判最后的 x == y
}
return (dfs(x, y - x * cnt) * (qpow(p0, cnt) % mod)) % mod;
}
int cnt = x / y;
if (x % y == 0)
{
cnt--;
}
return ((dfs(x - y * cnt, y) - 1 + mod) % mod * qpow(p1, cnt) % mod + 1) % mod;
}
void solve()
{
cin >> x >> y >> a >> b >> c; // 赢的概率是 a / c 和 b / c
c = a + b; // 除去平局
// 逆元
p0 = a * qpow(c, mod - 2) % mod; // A赢
p1 = b * qpow(c, mod - 2) % mod; // B赢
cout << dfs(x, y) << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
I - Strange Binary
题意
给定非负整数\(n\)，问是否能构造出序列\(A\)使得\(\sum_{i=0}^{31}2^i*a_i = n\)，其中\(a_i\)满足：\(a_i = 1或0或 -1，a_i^2+a_{i+1}^2 \neq 0\)。有则输出任意满足要求的序列，否则输出\(NO\)。
思路
对于\(a_i\)，它代表的就是第\(i\)位上的\(1\)(\([0,31]\)位每一位上只有1个\(1\))，所以\(a_{31}\)必定是\(1\)，否则结果就一定是负数。而显然\(0, 0, 0, 1, 1\)等价于\(1,-1,-1,-1,1\)所以每个\(01\)结构都能这样凑出来，即对于第\(i\)位的\(1\)，可以转化成\(2^i = 2^{i+1} - 2^i\)，此时\(a_{i+1}=1，a_i = -1\)，这时又可以将第\(i+1\)位上的\(0\)抵消。构造过程中发现，\(4\)的倍数(末尾有两个以上连续的\(0\))，或者中间有两个以上连续的\(0\)，不能构造。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n;
cin >> n;
vector<int> a(32);
int idx = 0;
while (n)
{
if (n & 1)
{
a[idx++] = 1;
}
else
{
a[idx++] = 0;
}
n >>= 1;
}
for (int i = 0; i <= 30; i++)
{
if (a[i] == 1 && a[i + 1] == 0) // 0，1可以凑成1，-1
{
a[i + 1] = 1;
a[i] = -1;
}
}
for (int i = 0; i < 31; i++)
{
if (a[i] == 0 && a[i + 1] == 0) // 非法
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
for (int i = 0; i <= 31; i++)
{
cout << a[i] << ((i + 1) % 8 ? " " : "\n");
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
J - Stacking of Goods
题意
\(n\)个物品，每个物品有重量\(w\)、体积\(v\)和可压缩度\(c\)三种属性。你要讲物品堆叠，一个物品在堆叠后的体积是\(v_i-c_i*W\)，其中\(W\)是其上方所有物品的重量之和。求所有物品堆叠后总体积的最小值。
思路
代码
点击查看代码
L - 502 Bad Gateway
题意
思路
代码
点击查看代码