过题数 |
排名 |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
4 |
258 |
B |
√ |
√ |
|
√ |
|
√ |
|
|
|
1 2 3 4 5 6
| |过题数|排名|A|B|C|D|E|F|G|H|I|J|K|L|M| |-----|----|-|-|-|-|-|-|-|-|-|-|-|-|-| | | | | | | | | | | | | | | | | √ 赛时过了 B 补题过了
|
A Tree
题目要求你改变一些点的黑白(可以不改变),按照颜色分为两个集合后,你需要最大化 x∈V1∑y∈V2∑val(x,y) 最小, val(x,y) 表示两点之间路径中最大的边的边权。
这种题应该一开始就想到重构树,这样一条边的贡献就转化为了父节点到子节点之间,然后我们简单跑一个树形背包就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=6060; const int inf=1e18;
int cost[maxn],col[maxn]; int val[maxn]; int sz[maxn]; int f[maxn][maxn],g[maxn]; int ans,n;
vector <int> c[maxn];
struct Graph{ struct edge{ int x,y,z; bool operator <(const edge mmm) { return z<mmm.z; } }e[maxn]; int f[maxn]; void init() {for(int i=1;i<=n*2;i++) f[i]=i;} int getf(int x) { if(x==f[x]) return x; return f[x]=getf(f[x]); } }G;
void dfs(int t) { if(c[t].empty()) { sz[t]=1; f[t][col[t]]=0; f[t][col[t]^1]=-cost[t]; return ; } f[t][0]=0; for(auto v : c[t]) { dfs(v); memcpy(g,f[t],sizeof(f[t])); for(int i=0;i<=n;i++) f[t][i]=-inf; for(int i=0;i<=sz[t];i++) for(int j=0;j<=sz[v];j++) { int cross=i*(sz[v]-j)+j*(sz[t]-i); f[t][i+j]=max(f[v][j]+g[i]+cross*val[t],f[t][i+j]); ans=max(ans,f[t][i+j]); } sz[t]+=sz[v]; } }
signed main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) cin>>col[i]; for(int i=1;i<=n;i++) cin>>cost[i]; for(int i=1;i<n;i++) cin>>G.e[i].x>>G.e[i].y>>G.e[i].z; sort(G.e+1,G.e+n); G.init(); int tot=n; for(int i=1;i<n;i++) { int tx=G.getf(G.e[i].x); int ty=G.getf(G.e[i].y); c[++tot].push_back(tx); c[tot].push_back(ty); G.f[tx]=G.f[ty]=tot; val[tot]=G.e[i].z; } n=tot; dfs(n); cout<<ans<<'\n'; }
|
B Distance
dp做法
定义 f[i][j] 表示 A 的第 i 个元素匹配到 B 的第 j 个元素的所有的可能的花费之和。可以有转移方程
$f_{i,j}=cost(a_i,b_j)*G(i,j) + \sum_{x<i,y<i}\limits f_{x,y} $
G(i,j) 表示匹配的方案数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2020; const int modp=998244353;
int a[maxn],b[maxn],n; int f[maxn][maxn],fsum[maxn][maxn],ans; int g[maxn][maxn],gsum[maxn][maxn];
int chg(int x,int y) { return abs(x-y); }
signed main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; sort(a+1,a+n+1); sort(b+1,b+n+1); gsum[0][0]=1; for(int i=1;i<=n;i++) gsum[i][0]=gsum[0][i]=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { g[i][j]=gsum[i-1][j-1]; f[i][j]=(fsum[i-1][j-1]+g[i][j]*chg(a[i],b[j]))%modp; ans=(ans+f[i][j])%modp; fsum[i][j]=(fsum[i][j-1]+fsum[i-1][j]-fsum[i-1][j-1]+f[i][j])%modp; gsum[i][j]=(gsum[i][j-1]+gsum[i-1][j]-gsum[i-1][j-1]+g[i][j])%modp; } cout<<ans<<'\n'; }
|
数学做法
咕咕咕。
C idol!!
做法比较奇怪,用的是找规律的,可以证明 5 的个数一定低于 2 的个数(否则只有2) ,因此就只需要寻找这个表达式中有多少个 5 就可以了。
对于奇数,我们考虑能从中寻找到多少个 5 。这个表达式大概可以写成
sum=(5)1+(7)1+(9)1+...+(15)2+...+(25)3 可以看见满10一个周期加上一
对于偶数,也有一样的规律。注意 _int128
不能够使用标准io。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include<bits/stdc++.h>
#define int __int128
using namespace std;
int ans=0,n; long long tmpans[]={0,0,0,0,0,1,1,2,2,3,4,5,6,7,8,10};
int getsum(int x,int tmp) { if(x<=0) return 0; int basans=tmp*x*(x+1)/2; return basans; }
void read(int &x) { x=0; char t=getchar(); while(!isdigit(t)) t=getchar(); while(isdigit(t)) x=x*10+t-'0',t=getchar(); }
void print(int x) { if(x>=10) print(x/10); putchar(x%10+'0'); }
signed main() {
read(n); int tmp=5; if(n<=15) { cout<<tmpans[n]<<'\n'; return 0; } while(tmp<=n) { int sz=0; int lk=((n-tmp)/(tmp*2)*(tmp*2))+tmp; sz=(n-lk)/2+1; ans+=sz*((n-tmp)/(tmp*2)+1); ans+=getsum((n-tmp)/(tmp*2),tmp); tmp*=5; } tmp=10; while(tmp<=n) { int sz=0; int lk=(n-tmp)/tmp*tmp+tmp; sz=(n-lk)/2+1; ans+=sz*((n-tmp)/tmp+1); ans+=getsum(lk/tmp-1,tmp/2); tmp*=5; } print(ans);
}
|
E Sequence
在 [l,r) 中找到 k−1 个数,使得 [l,k1]+[k1+1,k2]...[kk−1,r] 都是偶数。
直接利用前缀和即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include<bits/stdc++.h> #define int long long
using namespace std;
const int maxn=101000;
int n,m,a[maxn]; int cnt1,cnt2,T; int place[maxn];
signed main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cnt1=cnt2=0; place[0]=++cnt2; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]+=a[i-1]; if(a[i]%2==0) { place[i]=++cnt2; } else { place[i]=++cnt1; } } for(int i=1;i<=m;i++) { int l,r,k; cin>>l>>r>>k; if(a[l-1]%2!=a[r]%2) cout<<"NO\n"; else { if(place[r]-place[l-1]>=k) cout<<"YES\n"; else cout<<"NO\n"; } } } }
|