国庆集训 1105-1106

思维难度都好高啊~

树 tree

#include<bits/stdc++.h>
using namespace std;
int const N = 1e7 + 10;
int n, t[N], f[N][2], lin[N], ans, len;
struct edge{
    int y, next;}e[N<<1];void insert(int x, int y){
    e[++len].y = y;e[len].next = lin[x];lin[x] = len;
}void dfs(int p, int fa){
    f[p][t[p]] = 1;for(int i = lin[p];i;i = e[i].next) {
    int y = e[i].y;if(y == fa)  continue;dfs(y, p);f[p][0] += f[y][0];f[p][1] += f[y][1];}ans += abs(f[p][0] - f[p][1]);
}int main() {
    scanf("%d", &n);for(int i = 1, ti;i <= n; i++) {
    scanf("%d", &ti);t[i] = (ti+1) & 1;}for(int i = 1, v, u;i < n;i++) {
    scanf("%d%d", &u, &v);insert(u, v); insert(v, u);}dfs(1, 0);printf("%d\n", ans);return 0;
} 

洗衣服 wash

图文并茂的T2题解

正解

#include<bits/stdc++.h>
#define ll long long
using namespace std;
//这是一坨神奇的快读~~时限太小
char ch, B[1 << 20], *S = B, *T = B;
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 20, stdin), S == T) ? 0 : *S++)
inline ll read(){
    int sum=0,flag=1;char c;for(;c<'0'||c>'9';c=getc())if(c=='-') flag=-1;for(;c>='0'&&c<='9';c=getc())sum=(sum<<1)+(sum<<3)+c-'0';return sum*flag;
}ll n, x, m,ans[10000010], sum;int main() {
    n = read();  x = read();  m = read();for(int i = 1; i <= n; i++) {
    ll t = read();ll tmp = x*(n-i+1);if(tmp > m) ans[m] = max(ans[m], t+m); else ans[tmp] = max(ans[tmp], t+tmp); }for(int i = m; i >= 1; i--)ans[i] = max(ans[i+1]-1, ans[i]);ll k = ans[1];for(int i = 1; i <= m; i++)k = max(k, ans[i]),i==1 ? sum = k : sum ^= k*i;printf("%lld", sum);return 0;	
}

同机房大佬hzk的解法

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10000000;char buf[1<<20],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
int Ri(){
    int x=0;char c=getchar();for (;c<'0'||c>'9';c=getchar());for (;c<='9'&&c>='0';c=getchar()) x=x*10+c-'0';return x;
}int n,x,m,a[N+9];void into(){
    n=Ri();x=Ri();m=Ri();for (int i=1;i<=n;++i) a[i]=Ri();
}//对于 x,y 确定的情况，必然存在一种最优策略满足 [1,p) 用手洗，[p,n] 用洗衣机洗 
//分界点 p 随着 y的增大而减小 int p,now,nxt,sum;
//p -> 当前最优的分界点
//now -> p 作为分界点的答案 
//nxt -> p-1 作为分界点的答案 
//sum -> 区间 [p-1,n] 都用洗衣机会空出多少时间 int Get_ans(int y){
    for (;p&&a[p]+y>nxt;){
    now=nxt;--p;//更新 now,p if (x<=(sum+=a[p+1]-a[p])) sum-=x;else nxt+=x-sum,sum=0;//更新 sum }return max(now,p?a[p]+y:0);//now -> 仅仅表示用洗衣机洗的答案，并不包括用手洗的答案 
}LL ans0;void work(){
    now=0;nxt=a[p=n]+x;//初始化 for (int i=1;i<=m;++i) ans0^=(LL)i*Get_ans(i);
}void outo(){
     printf("%lld\n",ans0);}int main(){
    into();work();outo();return 0;
}

环 ring

1.字母含义

$r$ 红球个数

$g$ 绿球个数

$b$ 蓝球个数

$p$ 红球间绿球至少存在的个数

$q$ 绿球间篮球至少存在的个数

$len$ 所有球的总和

2.分类讨论

1. $g$ 等于零

两个条件都不存在，就是全排列的个数，控制红球1号为第一位，则返回 $fac[len?1]$

2. $r$ 等于零

所有的位置，假设我们把 $q$ 个蓝球和 $1$ 个绿球捆绑，那么 $len?g?p$ 就是绿球和自由的蓝球可以填的位置，因为控制了第一位为绿球1号，所以方案数为从 $len?1?g?q$的位子选择 $g?1$ 个

控制绿球1号为第一位，那么排列数就是方案数乘 $fac[g?1]$ * $fac[b]$

返回 $C(len?1?g?q,g?1)$ * $fac[g?1]$ * $fac[b]$

3. $b$ 等于零

类似于 $2$

返回 $C(len?1?r?p,r?1)$ * $fac[r?1]$ * $fac[g]$

4. $q$ 等于零

$sum$ $=$ $fac[r?1]$ * $fac[g]$ * $fac[b]$

$sum$ * $C(len?1,b)$ * $C(len?1?b?r?p,r?1)$

也就是说只需要考虑红球与绿球的关系即可

首先控制红球1号为第一位

在剩下的 $len?1$ 个位置中选择 $b$ 个位置放蓝球

然后就是在len=len-b的情况做第 $3$ 种情况

5. $p$ 等于零

相当于 $4$

6. 都不为0

ll k=0;
ans = sum * C(g-r*p+r-1, r-1);//sum是排列数
//g-r*p为剩下自由的绿球，利用隔板法分成r段，相当于枚举每两个红球之间的绿球数
for(ll i = 0, j = 1; i <= r; i++, j = j*q)//j其实就是q的i次方k += j *  C(r, i) * C(（b-g*q)+g+r-i-1, g+r-i-1);
答案为 ans*k

按 $3$ 做法放完红球和绿球，保证红绿球合法，情况为 $C(g?r?p+r?1,r?1)$

因为红球对于蓝球没有影响，所以我们只要再使得绿蓝球合法即可，绿蓝球合法的情况为k种，所以最后答案为 $k?ans$ ( $ans$ 为红绿球合法的情况乘上 $sum$ )

我们先在每一个绿色后面放 $q$ 个蓝球。

在【绿】【绿】这样的排列情况下，中间只可能存在 $1$ 个或 $0$ 个红球，我们通过枚举，有 $i$ 个红球在绿绿之间但左端存在的蓝球数小于$q$ ，我们叫这样的区间为AAA区间。

构造不满足的情况：【绿】【绿】之间一定有 $q$ 个蓝球（上面的构造）, 对于每一个【绿】【绿】区间，红球都有q种选择使得这个区间是AAA区间，所以乘以 $j$ （$q$ 的 $i$ 次方）。

因为红球本身具有不同的编号，所以还要乘以 $C(r,i)$

对于剩下的$（b?g?q)$ 个蓝球，可以随意放在非AAA区间

关于非AAA区间，$r?i$ 个红球与 $g$ 个绿球两两之间的空隙皆构成非AAA区间，所以利用隔板法把剩余的蓝球划分成 $g+r?i$ 个区间，因为可以为0，所以前面要加上 $g+r?i$ ，因为隔板枚举空隙，所以还需要再减 $1$

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = 3e6+5;
const ll mod = 1e9+7;
int r, g, b, p, q, len, T;
ll fac[N], inv[N], ans;
ll M(ll a){
    return a%mod;}
ll mul(ll a, ll b){
    return M(a*b);}
ll add(ll a, ll b){
    return M(a+b);}
ll sub(ll a, ll b){
    return M(a-b+mod);}
ll P(ll a, ll b){
    ll c=1;while(b){
    if(b&1)c=mul(c,a);b>>=1;a=mul(a,a);}return c;}inline void prep() {
    fac[0] = 1;for(int i = 1; i < N; i++)fac[i] = mul(fac[i-1], i);inv[N-1] = P(fac[N-1], mod-2);for(int i = N-2; i>=0; i--)inv[i] = mul(inv[i+1], i+1);
}inline ll C(ll n, ll m){
     if(n == m) return 1;if(m > n) return 0;return mul(inv[n-m], mul(fac[n], inv[m])); 
}inline ll get_ans() {
    if(!g) return fac[len-1];if(!r) return mul(C(len-g*q-1, g-1), mul(fac[g-1], fac[b]));ll sum  = mul( fac[r-1], mul(fac[g], fac[b]));ll sum1 = mul( fac[g-1], mul(fac[r], fac[b]));if(!b) return mul(mul(fac[r-1], fac[g]), C(len-r*p-1,r-1));if(!q) return mul(mul( sum, C(len-1, b) ), C(len-1-b-r*p, r-1));if(!p) return mul(mul(sum1, C(len-1, r) ), C(len-1-r-g*q, g-1)); ans = mul(sum, C(g-r*p+r-1, r-1));  ll k=0;for(ll i=0,j=1; i <= r; i++, j = mul(j, q))k = M( k+mul(mul(j,C(r, i)), C(b-g*q+r+g-i-1,g+r-i-1)) );ans = mul(ans, k);return ans;
} int main() {
    scanf("%d", &T);prep();while( T-- ) {
    scanf("%d%d%d%d%d", &r, &g, &b, &p, &q);len = r+g+b;ans = 0;printf("%lld\n", get_ans());}return 0;
}

蒟蒻10分代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;int n, m, cnt;
const int N = 5e5;
int a[N][30];
bool bis[N], pis[N];
int vis[N][105], sum[N]; 
priority_queue< int, vector<pair<int, int > >, greater< pair<int, int> > > q1, q2;int main() {
    scanf("%d%d", &n, &m);char ch[n-m+10][m+10];for(int i = 1; i <= n-m+1; i++) scanf("%s", ch[i]+1);//输入 for(int i = 1; i <= n-m+1; i++) {
    int k1 = 0, k2 = 0;for(int j = 1; j <= m; j++) {
    int x = ch[i][j]-'a'+1;if(j < m) {
    if(a[k1][x]) k1 = a[k1][x];else a[k1][x] = ++cnt, k1 = cnt;if(j == m-1) q1.push(make_pair(k1, i));}if(j > 1) {
    if(a[k2][x]) k2 = a[k2][x];else a[k2][x] = ++cnt, k2 = cnt;if(j == m) q2.push(make_pair(k2, i));}}}int x3=0, y3=0;while(!q2.empty()) {
    int x2 = q2.top().first;int y2 = q2.top().second;if(x2 == x3) {
    for(int i = 1; i <= sum[y3]; i++)vis[y2][i] = vis[y3][i];sum[y2] = sum[y3];}else {
    while(!q1.empty()) {
    int x1 = q1.top().first;int y1 = q1.top().second;if(x1 == x2 && y1 != y2) vis[y2][++sum[y2]] = y1, pis[y1] = 1, q1.pop();if(x1 != x2) break;}}x3 = x2; y3 = y2;q2.pop();}//处理vis数组 int k = 1;for(int i = 1; i <= n-m+1 && !k; i++) if(!pis[i]) k = i;bis[k] = 1;for(int i = 1; i <= n-m; i++) {
    for(int j = 1; j <= sum[k]; j++) if(!bis[vis[k][j]] && (sum[vis[k][j]] || i == n-m)) {
    printf("%c", ch[k][1]);bis[vis[k][j]] = 1;k = vis[k][j];break;}}for(int i = 1; i <= m; i++) printf("%c", ch[k][i]);//输出 return 0;
} 

欧拉路AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1e6+10;
int n, m, t, l, r, root = 1, flag, f[N];
char s[N];
string c[N], ans;
map < string, int > b;
vector< int > a[N];inline void put(string x, string y) {
    if(!b[x]) b[x] = ++t, c[t] = x; if(!b[y]) b[y] = ++t, c[t] = y;//给新出现的字符串一个编号，记录编号对应的字符串 l = b[x], r = b[y];f[l]--;   f[r]++;//有向图的起点需要满足出度减入度为1 a[r].push_back(l);//加入可以去到的点的编号 
}inline void dfs(int x) {
    while(a[x].size()) {
    //如果还可以往下走 int y = a[x].back();//一个可以到的地方 a[x].pop_back();//把这个值去掉 dfs(y); }if(flag) ans.push_back(c[x][m-2]);//没到最后 else flag = 1, ans = c[x];//到最后了 
}int main() {
     scanf("%d%d", &n, &m);for(int i = 1; i <= n-m+1; i++) {
    scanf("%s", s+1);string x,y;for(int j = 1; j <= m; j++) {
    if(j < m) x += s[j];//x是前缀 if(j > 1) y += s[j];//y是后缀 }put(x,y);}for(int i = 1; i <= t; i++)if(f[i]==1) {
     root = i; break; }//找起点dfs(root);cout<<ans;return 0;
}

未匹配点：没有对面的点与之匹配
可匹配点：有对面的点与之匹配，但是对面的点也有别的选择
必然匹配点：有对面的点与之匹配，且对面的点仅可以与这点匹配
不难发现，如果一个点在二分图上是必然匹配点，那么先手必胜，否则后手胜。
然后跑一遍最大匹配， 再判断每个点是否是最大匹配点即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e4+10;
struct psx{
    int next, y;} e[N<<1];
int len, n, m, old, lin[N], cp[N];
bool vis[N];inline void insert(int xx, int yy) {
    e[++len].next = lin[xx];lin[xx] = len;e[len].y = yy;
} inline int dfs(int k) {
    for(int i = lin[k]; i; i = e[i].next) {
    int y = e[i].y;if(!vis[y] && y != old) {
    vis[y] = 1;if(!cp[y] || dfs(cp[y])) {
     cp[y] = k; cp[k] = y; return 1; }}}return 0;
}int main() {
     scanf("%d%d", &n, &m);for(int i = 1, u, v; i <= m; i++) {
    scanf("%d%d", &u, &v);insert(u, v);insert(v, u);}for(int i = 1; i <= n; i++)if(!cp[i]) memset(vis, 0, sizeof vis), dfs(i);//最大匹配for(int i = 1; i <= n; i++) {
    if(!cp[i]) puts("Elephant");//如果是未匹配点else {
    int x = cp[i];old = i;cp[i] = cp[x] = 0;memset(vis, 0, sizeof vis);if(dfs(x)) puts("Elephant");//如果是可匹配点else puts("Hamster"), cp[i] = x, cp[x] = i;//如果是必然匹配点}}return 0;
}

来自rfy大佬的题解

#include<bits/stdc++.h>
#define ll long long
using namespace std;const ll mod = 998244353;
const int N = 1e7+10;
int T, n, m;
ll sum;
ll fac[N], inv[N];
ll M(ll a){
    return a%mod;}
ll mul(ll a, ll b){
    return M(a*b);}
ll add(ll a, ll b){
    return M(a+b);}
ll sub(ll a, ll b){
    return M(a-b+mod);}
ll P(ll a, ll b){
    ll c=1;while(b){
    if(b&1)c=mul(c,a);b>>=1;a=mul(a,a);}return c;}inline void prep() {
    fac[0] = 1;for(int i = 1; i < N; i++)fac[i] = mul(fac[i-1], i);
}int main() {
    scanf("%d", &T);prep();while( T-- ) {
    scanf("%d", &n);sum = 1; m = 0;for(int i = 1, a; i <= n; i++) {
    scanf("%d", &a);sum = mul(sum, fac[a]);m += a;} sum = mul(sum, mul(P(fac[m], mod-2), P(n, m)));printf("%lld\n", sum);}return 0;
}