我的首站 本来想着练练手 拿铜牌血赚 打铁不亏
结果 保底铜牌 要是G题做出来应该可以冲击一下银牌
https://codeforces.com/gym/104008
A. Lily
签到题：所有不在 L 旁的字符替换为 C 即可。
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int n; scanf("%d", &n);
char s[2000];
cin >> (s + 1);
for(int i = 1; i <= n; i++) {
if(s[i] == 'L') {
if(s[i - 1] != 'L') s[i - 1] = '!';
if(s[i + 1] != 'L') s[i + 1] = '!';
}
}
for(int i = 1; i <= n; i++) {
if(s[i] == '.') cout << "C";
else if(s[i] == '!') cout << ".";
else cout << "L";
}
return 0;
}
C. Array Concatenation
可以发现，只要使用了第二种操作，无论什么时候第一次使用，最终的前缀和之和都是相同的，所以只有两种本质不同的前缀和之和
时间复杂度 O(1)
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lld;
const int N = 100005;
const lld p = 1000000007;
lld sum[N], a[N], tot[N];
lld powe(lld a, lld b) {
lld base = 1;
while(b) {
if(b & 1) base = base * a % p;
a = a * a % p; b >>= 1;
}
return base;
}
lld pos_t = 0, neg_t = 0, squ = 0;
lld ans1 = 0, ans2 = 0;
int main() {
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
squ += a[i]; squ %= p;
}
for(int i = 1; i <= n; i++) {
sum[i] = (sum[i - 1] + a[i]) % p;
pos_t = (pos_t + sum[i]) % p;
}
for(int i = n; i >= 1; i--) {
tot[i] = (tot[i + 1] + a[i]) % p;
neg_t = (neg_t + tot[i]) % p;
}
squ = squ * n % p;
ans1 = ans2 = squ * powe(2, m - 1) % p * (powe(2, m) - 1 + p) % p;
ans1 = (ans1 + powe(2, m - 1) * pos_t % p) % p;
ans1 = (ans1 + powe(2, m - 1) * neg_t % p) % p;
ans2 = (ans2 + powe(2, m) * pos_t % p) % p;
printf("%lld", max(ans1, ans2));
return 0;
}
E. Draw a Triangle
分析：
我们队做法和题解不一样
首先很容易想到对 长a 宽b 同除以gcd(a,b)
因为每段都是gcd(a,b)为循环 只要我们处理处一段即可
此时 长为n 宽为m 且（m，n互质）
斜线的一次函数为 y=(m/n)*x
x=n*y/m
当y=1 时 x=n/m
当y=2 时 x=2n/m
当y=3 时 x=3n/m
当y=k 时 x=kn/m
很明显 我们要最小化 kn%m
但是值不能为0 因为点不能在线上 因为y取值为[1,m] 所以可以保证1出现 所以最小值为1
kn≡1(mod m) 也就是说k为n模m意义下的逆元 用exgcd就能求出来了
注意：一定要特判m=1的情况 任何数模1都是0！！！比赛罚时好久！！
官方题解更简便
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int T;
ll n,m,k,yy;
ll ansx,ansy;
ll gcd(ll aa,ll bb){
if(!bb)return aa;
return gcd(bb,aa%bb);
}
ll exgcd(ll aa,ll bb,ll &x,ll &y){
if(!bb){
x=1,y=0;
return aa;
}
ll d=exgcd(bb,aa%bb,x,y);
ll t=x;
x=y;
y=t-aa/bb*y;
return d;
}
ll inv(ll A,ll M){
ll xx,yy;
assert(exgcd(A,M,xx,yy)==1);
return (xx%M+M)%M;
}
int main(){
cin>>T;
for(int i=1;i<=T;i++){
ll x1,y1,x2,y2;
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
n=abs(x2-x1),m=abs(y2-y1);
if(!n)ansx=x1-1,ansy=y1;
if(!m)ansx=x1,ansy=y1+1;
if(!n||!m){
printf("%lld %lld\n",ansx,ansy);
continue;
}
ll gg=gcd(n,m);
n/=gg;m/=gg;
k=inv(n,m);
ll t=k*n/m;
if(m==1)t=-1;
if((x1-x2)*(y1-y2)>0)
printf("%lld %lld\n",t+min(x1,x2),k+min(y1,y2));
else printf("%lld %lld\n",max(x1,x2)-t,k+min(y2,y1));
}
return 0;
}
M. Youth Finale
队友做的貌似也挺简单的
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
typedef long long lld;
const int N = 300005;
deque<int> q;
lld a[N];
lld ans = 0;
lld c[N];
int lowbit(int x) {
return x & -x;
}
void add(int x, int k) {
for(; x < N; x += lowbit(x)) c[x] += k;
}
lld ask(int x) {
lld que = 0;
for(; x; x -= lowbit(x)) que += c[x];
return que;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]); q.push_back(a[i]);
}
for(int i = n; i >= 1; i--) {
ans += ask(a[i]);
add(a[i], 1);
}
printf("%lld\n", ans);
char s[600005];
cin >> (s + 1);
int flag = 0;
for(int i = 1; i <= m; i++) {
if(s[i] == 'R') {
flag = flag ^ 1;
ans = 1ll * n * (n - 1) / 2 - ans;
} else {
lld now = 0;
if(!flag) {
now = q.front();
q.pop_front(); q.push_back(now);
} else {
now = q.back();
q.pop_back(); q.push_front(now);
}
// printf("----->%lld\n", now);
ans = ans + n - now - (now - 1);
}
printf("%lld", ans % 10);
}
return 0;
}
G. Group Homework
分析：
其实很好考虑的 最优解一定是 两条互不相交的路径最大 或者 一个点连着四条路
https://codeforces.com/problemset/problem/633/F
板子题目 找两条互不相交路径的最大值
dp[maxn];u为根的子树 两条不相交的链最大值
f[maxn];u为根的子树 一条链的最大值
g[maxn];u为根的子树 以u为终点的一条链 和一条链的最大值
d[maxn];u为根的子树 以u为终点的一条链 的最大值
转移过程是 按照次序不断跟新儿子 ！！！
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
int n;
ll a[maxn];
ll dp[maxn];
ll f[maxn];
ll g[maxn];
ll d[maxn];
vector<int>Q[maxn];
void dfs(int,int);
int main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int u,v,i=1;i<n;i++){
scanf("%d%d",&u,&v);
Q[u].push_back(v);
Q[v].push_back(u);
}
dfs(1,1);
cout<<dp[1];
return 0;
}
void dfs(int u,int fa){
dp[u]=f[u]=g[u]=d[u]=a[u];
ll maxx=0;
for(int i=0;i<Q[u].size();i++){
int to=Q[u][i];
if(to==fa)continue;
dfs(to,u);
dp[u]=max(dp[u],dp[to]);
dp[u]=max(dp[u],g[u]+d[to]);
dp[u]=max(dp[u],f[u]+f[to]);
dp[u]=max(dp[u],g[to]+d[u]);
f[u]=max(f[u],f[to]);
f[u]=max(f[u],d[to]+d[u]);
g[u]=max(g[u],g[to]+a[u]);
g[u]=max(g[u],d[to]+a[u]+maxx);
g[u]=max(g[u],d[u]+f[to]);
d[u]=max(d[u],d[to]+a[u]);
maxx=max(maxx,f[to]);
}
}
回到本题来 第一种情况我们算解决了 第二种情况怎么办？
很好想到维护每个点的前四大的值 但是其中前四大值其中有来自于父亲节点 换根dp再维护一个pre就好
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=2e5+5;
int n;
ll Ans;
ll a[maxn];
ll dp[maxn];
ll f[maxn];
ll g[maxn];
ll d[maxn];
vector<int>Q[maxn];
void dfs(int,int);
void dff(int,int,ll);
int main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int u,v,i=1;i<n;i++){
scanf("%d%d",&u,&v);
Q[u].push_back(v);
Q[v].push_back(u);
}
if(n==1){
cout<<0;
return 0;
}
dfs(1,1);
dff(1,1,0);
printf("%lld",max(Ans,dp[1]));
return 0;
}
void dfs(int u,int fa){
dp[u]=f[u]=g[u]=d[u]=a[u];
ll maxx=0;
for(int i=0;i<Q[u].size();i++){
int to=Q[u][i];
if(to==fa)continue;
dfs(to,u);
dp[u]=max(dp[u],dp[to]);
dp[u]=max(dp[u],g[u]+d[to]);
dp[u]=max(dp[u],f[u]+f[to]);
dp[u]=max(dp[u],g[to]+d[u]);
f[u]=max(f[u],f[to]);
f[u]=max(f[u],d[to]+d[u]);
g[u]=max(g[u],g[to]+a[u]);
g[u]=max(g[u],d[to]+a[u]+maxx);
g[u]=max(g[u],d[u]+f[to]);
d[u]=max(d[u],d[to]+a[u]);
maxx=max(maxx,f[to]);
}
}
void dff(int u,int fa,ll pre){
ll max1=0,max2=0,max3=0,max4=0;
for(int i=0;i<Q[u].size();i++){
int to=Q[u][i];
if(to==fa)continue;
if(d[to]>=max1){
max4=max3;
max3=max2;
max2=max1;
max1=d[to];
}else if(d[to]>=max2){
max4=max3;
max3=max2;
max2=d[to];
}else if(d[to]>=max3){
max4=max3;
max3=d[to];
}else if(d[to]>max4)max4=d[to];
}
for(int i=0;i<Q[u].size();i++){
int to=Q[u][i];
if(to==fa)continue;
if(d[to]==max1)
dff(to,u,max(max2,pre)+a[u]);
else dff(to,u,max(max1,pre)+a[u]);
}
Ans=max(Ans,max(pre,max4)+max3+max2+max1);
}
热身赛 B. Underdetermined
题意：一个01方阵 构造一些1变成0 使得最终行列式≠0
分析：很好想到每一行每一列都有一个1即可满足题意
等着热身赛完了我才想出来做法
简单来说就是一个分配问题 网络流
建立源点S 对每一行连边 流量为1 每一行向 该行上1的点的列 连边流量为1 每一列向终点T连边 流量为1
跑一遍最大流 初始流量为n 检验最后流出是否也为n
L. Largest Unique Wins 构造 题意没理解 待补
标签：return,2022CCPC,int,ll,桂林,maxn,include,lld From： https://www.cnblogs.com/wzxbeliever/p/16851743.html