A
#include<bits/stdc++.h>
using namespace std;
int main(){
string s; cin>>s;
if(s[2]==s[3] && s[4]==s[5]) puts("Yes");
else puts("No");
return 0;
}
B
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
int res=0;
res+=n/500*1000;
n%=500;
res+=n/5*5;
cout<<res<<endl;
return 0;
}
C
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int w[N];
int main(){
int k, n; cin>>k>>n;
for(int i=1; i<=n; i++) cin>>w[i];
int res=0;
for(int i=1; i<=n; i++){
if(i==1) res=max(res, w[1]+k-w[n]);
else res=max(res, w[i]-w[i-1]);
}
cout<<k-res<<endl;
return 0;
}
D
枚举点对，分类讨论：两点都在环中，都不在环中，一个在一个不在
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
x*=s;
}
const int N=2021;
int n, x, y;
int res[N];
int main(){
read(n), read(x), read(y);
rep(i,1,n) rep(j,i+1,n){
if(i<x && j>y){
int v=j-i-(y-x-1);
res[v]++;
}
else if(i>y || j<x){
res[j-i]++;
}
else if(i>=x && j<=y){
int v=min(j-i, i+y-x+1-j);
res[v]++;
}
else{
if(i>=x && j>y){ // i inside
int v=min(y-i, i+y-x+1-y)+j-y;
res[v]++;
}
else{
int v=min(j-x, x+y-x+1-j)+x-i;
res[v]++;
}
}
}
rep(i,1,n-1) cout<<res[i]<<endl;
return 0;
}
E
取青苹果的最大 \(x\) 个和红苹果的最大 \(y\) 个还有全部的无色苹果按照美味度降序排序取最大的 \(x+y\) 个即可。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
x*=s;
}
const int N=2e5+5;
int x, y;
int a, b, c;
int bufa[N], bufb[N];
int buf[N], top;
ll res;
int main(){
read(x), read(y), read(a), read(b), read(c);
rep(i,1,a) read(bufa[i]);
rep(i,1,b) read(bufb[i]);
rep(i,1,c) read(buf[++top]);
sort(bufa+1, bufa+1+a, greater<int>());
sort(bufb+1, bufb+1+b, greater<int>());
rep(i,1,x) buf[++top]=bufa[i];
rep(i,1,y) buf[++top]=bufb[i];
sort(buf+1, buf+1+top, greater<int>());
rep(i,1,x+y) res+=buf[i];
cout<<res;
return 0;
}
F
换根DP。
先给出一个结论：
以 \(u\) 为根的大小为 \(n\) 的树，它的拓扑排序数为
\[\frac{n!}{\prod_{i\in[1,n]}sz_i}
\]
\(sz_i\) 表示以 \(u\) 为根的树中 \(i\) 点以及它的子树大小。
我们记 \(f_u = \prod_{i\in[1,n]} sz_i\) ，其中 \(u\) 为当前树的根节点，转移方程如下：
\[f_u = \frac{n}{sz_u} \frac{n-sz_u}{n} f_{fa}= \frac{n-sz_u}{sz_u} f_{fa}
\]
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
#define int long long
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
x*=s;
}
const int N=2e5+5, mod=1e9+7;
vector<int> g[N];
int n;
int f[N];
int fac[N];
void init(){
fac[0]=1;
rep(i,1,n) fac[i]=fac[i-1]*i%mod;
}
int fpow(int x, int p){
int res=1;
for(; p; p>>=1, x=x*x%mod)
if(p&1) res=res*x%mod;
return res;
}
int inv(int x){
return fpow(x, mod-2);
}
int sz[N];
void dfs(int u, int fa){
sz[u]=1;
for(auto i: g[u]){
if(i==fa) continue;
dfs(i, u);
sz[u]+=sz[i];
}
}
void dfs2(int u, int fa){
for(auto i: g[u]){
if(i==fa) continue;
f[i]=f[u]*(n-sz[i])%mod*inv(sz[i])%mod;
dfs2(i, u);
}
}
signed main(){
read(n);
rep(i,1,n-1){
int u, v; read(u), read(v);
g[u].pb(v), g[v].pb(u);
}
init();
dfs(1, -1);
f[1]=1;
rep(i,1,n) f[1]=f[1]*sz[i]%mod;
rep(i,1,n) debug(sz[i]);
dfs2(1, -1);
rep(i,1,n) cout<<fac[n]*inv(f[i])%mod<<endl;
return 0;
}