CCPC 网络预选赛 2024 个人题解
Dashboard - The 2024 CCPC Online Contest - Codeforces
L
签到题,
const int N = 1e3 + 10;
char s[N][N];
int n,m;
signed main() {
cin >> n >> m;
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= m;++j) {
cin >> s[i][j];
}
}
int ans = 0;
for (int i = 1;i < n;++i) {
for (int j = 1;j < m;++j) {
if (s[i][j] == 'c' && s[i][j+1] == 'c' && s[i+1][j] == 'p' && s[i+1][j+1] == 'c') {
++ans;
}
}
}
cout << ans;
return 0;
}
K
考虑分类讨论一下;
-
对于奇数的情况,先手显然可以通过一直取 1 的情况先手必胜。所以答案为
Alice
-
对于偶数的情况,我们不妨考虑一下
k 会带来的影响。一个比较直观的想法是,我们能不能通过巧妙的转化把偶数的情况转变为奇数的情况?发现是可以的,我们考虑
lowbit(n) ,如果k \geq lowbit(n) 的话,那么显然对于先手而言,我们可以通过不断取lowbit(n) 让整个局面等价于奇数的局面。这是因为,后手不论取任何数面对的都是一个取偶数次,即先手必败的局面。所以获胜的条件显然就是k \geq lowbit(n)
代码太简单没有难度不放了。
B
我们考虑怎样的序列是价值比较小的?
通过拆式子,我们不妨变为统计以下两个东西的最小值:
接下来考虑贡献,先考虑
此时贪心考虑,对于最大值而言,放在
接下来我们考虑方案数,观察到这个东西等价于你有
总时间复杂度
const int N = 1e3 + 10;
ll a[N],n,ans1,ans2 = 1,jc[N];
int buc[N*N];
signed main() {
read(n);
jc[0] = 1;
for (int i = 1;i <= n;++i) jc[i] = jc[i-1] * i % mod;
for (int i = 1;i <= n;++i) read(a[i]),buc[a[i]]++;
sort(a+1,a+1+n);
for (int i = 1;i <= n;++i) {
ans1 += a[i] * i;
}
reverse(a+1,a+1+n);
for (int i = 1;i <= n;++i) {
ans1 -= a[i] * i;
}
bool flag = 0;
for (int i = 1;i <= 1000000;++i) {
if (buc[i] == n) flag = 1;
if (buc[i]) ans2 = (ans2 * jc[buc[i]]) % mod;
}
if (!flag) ans2 = 2 * ans2 % mod;
printf("%lld %lld\n",ans1,ans2);
return 0;
}
D
这个题考虑,因为有
考虑区间 DP,
转移方程非常好写,考虑边界就可以:
时间复杂度
ll f[N][N][N],n,m;
char s[N],t[N];
signed main() {
scanf("%s\n%s\n",s+1,t+1);
n = strlen(s+1),m = strlen(t+1);
for (int i = 1;i <= n;++i) {
for (int l = 1;l <= m;++l) {
for (int len = 1;l + len - 1 <= m;++len) {
int r = l + len - 1;
f[i][l][r] = f[i-1][l][r] * 2 % mod;
for (int k = l;k < r;++k)
f[i][l][r] = (f[i][l][r] + f[i-1][l][k] * f[i-1][k+1][r]) % mod;
}
}
for (int j = 1;j <= m;++j) {
if (s[i] == t[j]) {
f[i][j][j]++;f[i][j][j] %= mod;
for (int l = 1;l <= j-1;++l) {
for (int len = 2;l + len - 1 <= m;++len) {
int r = l + len - 1;
f[i][l][r] = (f[i][l][r] + f[i-1][l][j-1] * f[i-1][j+1][r]) % mod;
}
f[i][l][j] = (f[i][l][j] + f[i-1][l][j-1]) % mod;
}
for (int r = j + 1;r <= m;++r) {
f[i][j][r] = (f[i][j][r] + f[i-1][j+1][r]) % mod;
}
}
}
}
printf("%lld\n",f[n][1][m]);
return 0;
}
G
义眼顶真鉴定为网络流,考虑如何建图?
我们不妨考虑一个经典的二分图建法:左部有
对于每个人(除了 1 号)而言,我们考虑一个能用于支付菜品的钱数上界
这个做法的正确性是基于,对上界进行的巧妙限制,因此一定不会出现第 1 条边没跑满但是其他边跑满了的情况。
struct edge {
ll c,f;
}e[N];
vector <pii> G[N];
int n,m,s,t,tot = -1,cur[N];
ll dis[N];
bool vis[N];
bool BFS() {
//memset(dis,0,sizeof dis);
memset(vis,0,sizeof vis);
queue <int> q;
q.push(s);dis[s] = 0;vis[s] = 1;
while (!q.empty()) {
int x = q.front();q.pop();
//printf("%d\n",x);
for (auto ed : G[x]) {
int y = ed.first,num = ed.second;
if (!vis[y] && e[num].c > e[num].f) {
vis[y] = 1;
dis[y] = dis[x] + 1;
q.push(y);
}
}
}
return vis[t];
}
ll DFS(int x,ll res) {
//printf("%d %d\n",x,res);
if (x == t || res == 0) return res;
ll now = 0;
for (int& i = cur[x];i < G[x].size();++i) {
pii ed = G[x][i];
int y = ed.first,num = ed.second;
if (dis[x] + 1 == dis[y]) {
ll f = DFS(y,min(res,e[num].c - e[num].f));
if (f > 0) {
e[num].f += f;
e[num ^ 1].f -= f;
now += f;
res -= f;
if (!res) break;
}
}
}
return now;
}
ll maxflow() {
int ans = 0;
while (BFS()) {
memset(cur,0,sizeof cur);
ans += DFS(s,1e15);
}
return ans;
}
ll a[N],v[N];
void addedge(int a,int b,ll c) {
G[a].push_back(mp(b,++tot));
e[tot].c = c;
G[b].push_back(mp(a,++tot));
}
signed main() {
read(n,m);
s = n + m + 1,t = n + m + 2;
ll lim = 0;
for (int i = 1;i <= n;++i) read(a[i],v[i]);
lim = v[1];
ll gol = 0;
for (int i = 1;i <= m;++i) {
ll a,b,c;
read(a,b,c);
if (a == 1 || b == 1) lim += c;
addedge(a,n+i,0x3f3f3f3f);addedge(b,n+i,0x3f3f3f3f);addedge(n+i,t,c);
gol += c;
}
lim = min(lim,a[1]);
bool flag = 0;
addedge(s,1,lim - v[1]);
for (int i = 2;i <= n;++i) {
if (lim <= v[i]) {
flag = 1;
break;
}
addedge(s,i,min(a[i],lim - 1) - v[i]);
}
if (maxflow() < gol || flag) puts("NO");
else puts("YES");
return 0;
}
E
对于每一层而言,第
对于第二问,我们仍然按层考虑,对于第
所以最后的答案就是:
const ll mod = 998244353;
const double eps = 1e-10;
ll ffpow(ll a,ll b) {ll ans = 1;while (b) {if (b & 1) ans = ans * a % mod;a = a * a % mod,b >>= 1;}return ans;}
ll ffpow2(ll a,ll b) {ll ans = 1;while (b) {if (b & 1) ans = ans * a;a = a * a,b >>= 1;}return ans;}
ll ans1,ans2,n,m;
signed main() {
read(n,m);
bool flag = 0;
for (int i = 0;i <= m;++i) {
if (ffpow2(26,i) >= n) flag = 1;
if (!flag) ans1 += min(ffpow2(26,i),n);
else ans1 += n;
}
ans1 %= mod;
for (int i = 0;i <= m;++i) {
ll p = (1 - ffpow(ffpow(26,i),mod-2) + mod) % mod;
p = ffpow(p,n);
ll val = (1 - p + mod) % mod * ffpow(26,i) % mod;
ans2 =( ans2 + val) % mod;
}
printf("%lld %lld\n",ans1,ans2);
return 0;
}
J
我不会线性基!完啦!幸好队友会
考虑交换这个东西,实际上是对
所以就直接贪心考虑,记我们构造出的线性基第
时间复杂度
int n,a[N],b[N],s[50];
void insert(int x) {
for (int i = 31;i >= 0;--i) {
if (x & (1 << i)) {
if (s[i]) x ^= s[i];
else {
for (int j = 0;j < i;++j) if (x & (1 << j)) x ^= s[j];
for (int j = i+1;j <= 31;++j) if (s[j] & (1 << i)) s[j] ^= x;
s[i] = x;
return ;
}
}
}
}
void solve() {
read(n);
memset(s,0,sizeof s);
int A = 0,B = 0;
for (int i = 1;i <= n;++i) read(a[i]),A ^= a[i];
for (int i = 1;i <= n;++i) read(b[i]),B ^= b[i];
for (int i = 1;i <= n;++i) {
insert(a[i] ^ b[i]);
}
int ans = max(A,B);
//for (int i = 0;i <= 31;++i) printf("%d ",s[i]);
//puts("");
for (int i = 31;i >= 0;--i) {
int bita = A & (1 << i),bitb = B & (1 << i);
if (!s[i]) continue;
int nval = max(A^s[i],B^s[i]);
if (nval < ans) {
ans = nval;
A ^= s[i];B ^= s[i];
}
}
printf("%d\n",ans);
}
I
首先将
考虑第
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
《黄英姑》剧情片高清在线免费观看:https://www.jgz518.com/xingkong/92516.html
《黄英姑》剧情片高清在线免费观看:https://www.jgz518.com/xingkong/92516.html
《超级飞侠第五季》国产动漫高清在线免费观看:https://www.jgz518.com/xingkong/25661.html
你的文章让我感受到了艺术的魅力,谢谢! https://www.yonboz.com/video/99406.html
你的文章内容非常卖力,让人点赞。 http://www.55baobei.com/hfdDObA75r.html
你的文章让我感受到了不一样的风景,谢谢分享。 http://www.55baobei.com/3inI0GQLJ9.html