Reinhart's problem set

DP

最长上升子序列模型

序列最大收益

题意

相邻元素的值分别为可以获得收益现在给一个序列,可以删除最多k个元素使得这个序列的收益之和最大.

状态表示

集合dp[i][j]

• 表示只考虑前i个数，共删除了j个数，且第i个数没被删掉

属性

• 最大值

状态计算

参考最长上升子序列模型

• 以第i的前一个数作为划分条件

  

i的前一个数有可能不存在，也有可能是第1个数…第i-1个数

所以得出此图

1～K中还有j-(i-k-1)个数没删，而由于右边的值已经确定（就是）所以根据前面状态表示的定义可以得出
$$
dp[k,j-(i-k-1)]+w[a_k,a_j]
$$

边界问题

第一个数和最后一个数是不用删的，因为是>=0的数，且1的左边，n的右边都已经没有数字了，删除1或n后不会产生新的数字组合，导致答案只减不增。

E - Equal Sentences

题意

给一段话S，每段话有n个词，给定另一段话T，这段话所包含的词以及和S是一模一样的，唯一不同的就是词的顺序，T[i]和S[i]不同但只能在的范围内不同，也就是说S[i]必须要在T[i-1,i+1]内找到和S[i]相同的词，这样就算是T和S almost equal（包含S自己）问能找到多少个这样的T

初步理解

不难发现只要将S相邻两个词交换位置就可以得到一种情况，并且如果相邻两个词若是相同的交换它们不会增加方案数

如下图所示

状态表示

集合dp[i]

• 长度为i的所有方案数

属性

• 方案数

状态计算

参考最长上升子序列模型

以i的前一个字符作为划分条件

如果前一个字符(s[i-1])和s[i]相等，那如果s[i]和s[i-1]交换不会增加方案数，所以dp[i]=dpi-1

如果前一个字符和s[i]不相等，s[i]和s[i-1]交换会增加方案数，s[i]和s[i-1]交换后s[i-1]变为s[i]，所以又新增了dp[i-2]的方案数，所以dp[i]=dp[i-1]+dp[i-2]

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
const int mod =1e9+7;
using namespace std;
#define PII pair<int,int>
const int N = 100005;
int dp[N];
string s[100005];
int main() {
    ios::sync_with_stdio();
    cin.tie();
    cout.tie();
    int t;
    cin>>t;

    while(t--){
        
        int n;
        cin>>n;
        for (int i = 1; i <=n ; ++i) {
            cin>>s[i];
        }
        dp[0]=1;
        for (int i = 2; i <=n ; ++i) {
            if(s[i]==s[i-1])dp[i]=dp[i-1];
            else{
                dp[i]=(dp[i-1]+dp[i-2])%mod;
            }
        }
        cout<<dp[n]%mod<<'\n';
    }
    return 0;
}

状态机模型

C.Hills

题意

现在有 n 座连在一起的山，高度从左到右分别为。现在你有一台挖掘机，每分钟可以令某一个 减一。你可以在 且 的山峰 盖房子。问对于 中的每个整数 ，盖 栋房子至少需要多长时间。

#include<cstdio>
#include<cstring>
int Min(int x,int y){return x<y?x:y;}
int Max(int x,int y){return x>y?x:y;}
int h[5050];
int f[5050][5050][2];
int main()
{
    memset(f,0x3f,sizeof(f));
    f[0][0][0]=0;//初始化
    f[1][1][1]=0;
    f[1][0][0]=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&h[i]);
    h[0]=0x3fffffff;
    for(int i=2;i<=n;++i)
    {
        f[i][0][0]=f[i-1][0][0];
        for(int j=1;j<=(i+1)/2;++j)
        {
            f[i][j][1]=Min(f[i-2][j-1][0]+Max(0,h[i-1]-h[i]+1),
                           f[i-2][j-1][1]+Max(0,h[i-1]-Min(h[i],h[i-2])+1));
            f[i][j][0]=Min(f[i-1][j][0],
                           f[i-1][j][1]+Max(0,h[i]-h[i-1]+1));
        }
    }
    for(int i=1;i<=(n+1)/2;++i)
        printf("%d ",Min(f[n][i][0],f[n][i][1]));
    return 0;
}

C. Unstable String

题意

t 组询问，每次给定一个仅包含字符11 或 00 或 ?? 字符串s。定义一个子串是不稳定的当且仅当子串中任意相邻两数均不相同，如 101010…101010…或 010101…010101…。其中 ? 可以变为 11 或 00 其中一种。请求出给定的 𝑠s 中最多可以有的不稳定子串个数。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 1e5;
const int M = 1e5;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;


int main() {
    //ios::sync_with_stdio(false);
    int t;
    cin >> t;

    while (t--) {
        int dp[200005][2] = {0};//dp[i][0]表示以i结尾的串，并且s[i]是0，有多少种符合要求的串
      ////dp[i][1]表示以i结尾的串，并且s[i]是1，有多少种符合要求的串
      //若s[i]是问号则取dp[i][1]和dp[i][0]的最大值（看把s[i]换成1还是换成0能取得更多的符合要求的串）
        char s[200005];
        cin >> (s + 1);

//        for(int i=1;i<=n;i++){
//            if(s[i]=='?')
//        }
        n = strlen(s + 1);

        for (int i = 1; i <= n; i++) {
            if(s[i]=='1')dp[i][1]=1;
            else if(s[i]=='0')dp[i][0]=1;
            else{
                dp[i][1]=dp[i][0]=1; //?可以变成0或1
            }

        }
        //cout<<(s+1)<<'\n';
        for (int i = 2; i <= n; i++) {
            if(s[i]=='0')dp[i][0]=dp[i-1][1]+1;
            else if(s[i]=='1')dp[i][1]=dp[i-1][0]+1;
            else{
                dp[i][1]=dp[i-1][0]+1;
                dp[i][0]=dp[i-1][1]+1;
            }
        }
        ll ans=0;
        for(int i=1;i<=n;i++) {
            ans += max(dp[i][0], dp[i][1]);//题目默认要求将?最优的变成0或1
        }
        cout << ans << '\n';

    }
    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

C. Gas Pipeline

题意

二进制01串。为1代表这个地方得是高度为2的柱子，为0代表可以为高度为1或者2的柱子。起点和终点柱子高度都为1。同时横向走的时候需要管道。柱子的单位花费是b，管道的单位花费是a。问怎么安排使得花费最小

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m, t;
ll dp[N][2];

//s[i]是第i个格子 dp[i][2]是第i根柱子 n个格子 n+1根柱子
void solve() {
    cin >> n;
    char s[N];
    ll a, b;
    cin >> a >> b >> s;
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = b;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            dp[i + 1][1] = min(dp[i][1] + a + 2 * b, dp[i][0] + 2 * a + 2 * b);
            dp[i + 1][0] = min(dp[i][1] + 2 * a + b, dp[i][0] + a + b);
        } else {
            dp[i + 1][1] = dp[i][1] + a + 2 * b;//如果第i个格子为1 第i根柱子不可能为1个单位
            dp[i + 1][0] = LLINF;//如果第i个格子为1 第i+1根柱子不可能为1个单位
        }
    }
    cout<<dp[n][0]<<'\n';

}

int main() {
    //ios::sync_with_stdio(false);
    t = read();
    while (t--) {
        solve();
    }

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

公共子序列模型

PTA 两个字符串的所有最长公共子序列

题意

求出所有的公共子序列，如果没有输出NO

思路

从DP[n][m]倒叙往后找

• 若a[i] b[j]相等，那这一位则是LCS中的一位，然后递推到i-1 j-1
• 若a[i] b[j]不相等，则需要比较DP[i-1][j] DP[i][j-1]大小
  • 若DP[i-1][j]!=D[i][j-1]则往较长的那个进行递推
  • 若DP[i-1][j]==D[i][j-1]则两个都进行递推

代码

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
char a[110], b[110];
int dp[110][110], n, m;
set<string> s1;

void go_back(int i, int j, string str) {
    while(i >= 1 && j >= 1) {
        if(a[i] == b[j]) {
            str = a[i] + str;
            i --, j --;
        } else {
            if(dp[i - 1][j] > dp[i][j - 1]) {
                i --;
            } else if(dp[i - 1][j] < dp[i][j - 1]) {
                j --;
            } else{
                go_back(i - 1, j, str);
                go_back(i, j - 1, str);
                return;
            }
        }
    }
    if(str.length()) s1.insert(str);
}

int main() {
    cin >> (a+1) >> (b+1);
    n = strlen(a+1), m = strlen(b+1);
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if(a[i]==b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }
    if(dp[n][m]==0)cout<<"NO";
    else {
        go_back(n, m, "");
        for (auto &x: s1) {
            cout << x << "\n";
        }
    }
}

C - chokudai

题意

算和子串p匹配的子序列个数

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;
ll a[N], b[N];
ll dp[N][9];

int main() {
    //ios::sync_with_stdio(false);
    char s[N];
    char p[] = "@chokudai";
    cin >> (s + 1);
    for(int i=0;i<=strlen(s+1);i++)dp[i][0]=1;
    for (int i = 1; i <= strlen(s+1); i++) {
        for (int j = 1; j <= 8; j++) {
            if (s[i] == p[j])dp[i][j] = (dp[i - 1][j - 1] +dp[i-1][j])%mod;
            else {
                dp[i][j] = dp[i - 1][j]%mod;
            }
        }
    }

    cout<<dp[strlen(s+1)][8];
    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

Nun Heh Heh Aaaaaaaaaaa

题意

给定一个序列s,求其[前缀是𝚗𝚞𝚗𝚑𝚎𝚑𝚑𝚎𝚑,后缀是>=1个a]的子序列个数

题解

先求出子序列为nunhehheh的个数,定义dp(i,j)为s的前i个字符中和nunhehheh匹配到第j个个数.然后预处理出i后面有多少个a,记为a[i],对于每个dp(i,9)乘再相加即可得到所有方案数

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#pragma GCC optimize(2)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC target("avx","sse2")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PIII pair<int,PII>
#define PLLL pair<ll,PLL>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 1e5 + 5;
const int M = 1e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;

inline ll read();

int n, m, t;

ll dp[N][15];
ll a[N];
ll poww[N];
void solve() {
    char s[N];
    string p = "@nunhehheh";
    cin >> (s + 1);
    ll len =strlen(s+1);
    for (int i = 0; i <= len+1; i++) {//初始化
        for (int j = 0; i <= 10; i++)dp[i][j] = 0;
        a[i] = 0;
    }
    for (int i = len; i >= 0; i--) {
        dp[i][0] = 1;//与s中第i个字符一个都不匹配的数量是1
        if (s[i] == 'a')a[i] = (a[i + 1] + 1) % mod;
        else {
            a[i] = a[i + 1];//预处理
        }
    }
    ll ans = 0;
    for (int i = 1; i <= len; i++) {
        for (int j = 1; j <= 9; j++) {
            if (s[i] == p[j])dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
            else {
                dp[i][j] = dp[i - 1][j] % mod;//算公共序列个数
            }
        }
    }
    for (int i = 0; i <= len; i++) {
        if (s[i] == 'h') {
            ans += (dp[i][8] * (poww[a[i]] - 1)) % mod;//注意这里是dp[i][8].如用dp[i][9]算答案会重复
        }
    }
    cout << ans % mod << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    poww[0]=1;
    for(int i=1;i<=1e5;i++){
       poww[i] =(poww[i-1]*2)%mod;
    }
    while (t--) {
        solve();
    }

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

树形DP

D. The Fair Nut and the Best Path

题意

到达一个点得到这个点的价值，经过一个边花费这个边的价值，求得到的最大价值

#include<iostream>
#include <vector>
 
#define ll long long
#define PLL pair<ll,ll>
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
int n;
int w[N];//存每个点快乐指数
vector<PLL > tree[N];
ll dp[N];
ll ans = 0;
 
void dfs(int u, int father) {
    ans = max(ans, dp[u]);
    for (int i = 0; i < tree[u].size(); i++) {
        int son = tree[u][i].first;
        if (son == father)continue;
        dfs(son, u);
        ans = max(ans , dp[son] + dp[u] - tree[u][i].second);//dp[son] + dp[u] - tree[u][i].second:倒v的形状,最大值+次大值
        dp[u] = max(dp[u], dp[son] + w[u] - tree[u][i].second);
        ans = max(ans, dp[u]);
 
    }
}
 
int main() {
    cin >> n;
 
    for (int i = 1; i <= n; i++)cin >> w[i];
    for (int i = 1; i <= n; i++)dp[i] = w[i], ans = max(ans, dp[i]);
    for (int i = 0; i < n - 1; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        tree[b].pb({a, c});
        tree[a].pb({b, c});
    }
    dfs(1, 0);
 
    for (int i = 1; i <= n; i++)ans = max(ans, dp[i]);
    cout << ans << '\n';
}

C. Parsa’s Humongous Tree

题意

有一颗树,每个结点都有一个取值范围,答案为所有相邻点的绝对值之差之和,现在要你确定每个点的值,求最大答案.

思路

贪心的要么取端点要么取右端点即可

#include <iostream>
#include <cstring>
#include <vector>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#pragma GCC optimize(2)
using namespace std;
typedef pair<int, int> PII;
#define debug(a) cout << #a << " " << a << endl
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
typedef long long ll;
inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while(ch < '0' || ch > '9') {
        if(ch == '-')p = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}
 
#define ll long long
const int N=200005,M=N*2;//无向图边数*2
int n;
int e[M],ne[M],h[N],idx;
int l[N],r[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
ll dp[N][2];
void dfs(int u,int fa){
    for (int i = h[u]; ~i ; i=ne[i]) {
        int j = e[i];
        if(j==fa)continue;//不能往上面搜
 
        dfs(j,u);
        dp[u][0]+=max(dp[j][0]+abs(l[u]-l[j]),dp[j][1]+abs(l[u]-r[j]));//dp[i][0]是第i个点取左边
        dp[u][1]+=max(dp[j][0]+abs(r[u]-l[j]),dp[j][1]+abs(r[u]-r[j]));//d p[i][1]是第i个点取右边
    }
}
int t;
int main(){
    t=read();
    while(t--) {
        memset(h,-1,sizeof h);
        memset(e,0,sizeof e);
        memset(ne,0,sizeof ne);
        memset(l,0,sizeof l);
        memset(r,0,sizeof r);
        memset(dp,0,sizeof dp);
        idx=0;
        cin >> n;
        for (int i = 1; i <=n ; ++i) {
            l[i]=read();
            r[i]=read();
        }
        for (int i = 0; i < n - 1; ++i) {
            int a, b;
            a=read();
            b=read();
            add(a, b);
            add(b, a);
        }
        dfs(1, -1);//以1为分界点
        cout<<max(dp[1][1],dp[1][0])<<'\n';
//        for (int i = 1; i <=n ; ++i) {
//            cout<<dp[i][0]<<' '<<dp[i][1]<<'\n';
//        }
//        cout<<'\n';
    }
}

计数类DP

D - FG operation

给一个N长度只有0到9的序列，做以下两个操作F：将（x+y）%10 G：将（x*y）%10（x和y是序列最前面的两个数），将结果放入序列最前面，直到只剩下一个数。算出每个数剩下的可能个数。

由于序列是固定的（作为y），所以dp枚举0到9所有数（作为x），将F和G的结果加入下一层，即可。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
using mint = modint998244353;

signed main(){
    ll n;cin>>n;
    vector<ll>a(n+1);
    for(ll i=1;i<=n;i++)cin>>a[i];
    mint dp[n+1][10];memset(dp,0,sizeof(dp));
    dp[1][a[1]] = 1;

    for(ll i=1;i<=n-1;i++){
        for(ll j=0;j<=9;j++){
            dp[i+1][(j+a[i+1])%10] += dp[i][j];
            dp[i+1][(j*a[i+1])%10] += dp[i][j];
        }
    }
    for(ll K=0;K<=9;K++){
        cout<<dp[n][K].val()<<endl;
    }
    return 0;
}

并查集/最小生成树/次小生成树

D - Sum of Maximum Weights

题意

思路

带权并查集:记录额外信息的并查集,此处记录的信息是集合的大小siz

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

struct stru {
    int u, v, w;
} edges[N];
int fa[N], siz[N];

bool cmp(stru a, stru b) {
    return a.w < b.w;
}

int find(int x) {
    if (fa[x] != x)fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int a, int b) {
    int x = find(a), y = find(b);
    if (x != y) {
        fa[x] = y;
        siz[y] += siz[x];
    }
}

int n, m;

int main() {
    //ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        siz[i] = 1;
    }
    sort(edges, edges + n - 1, cmp);

    ll ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ans += (ll) edges[i].w * (ll) siz[find(edges[i].u)] * (ll) siz[find(edges[i].v)];
        //cout<<ans<<'\n';
        merge(edges[i].u, edges[i].v);
    }
    cout << ans;

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

[PTA 社交集群][https://pintia.cn/problem-sets/1496741922278645760/problems/1496742006529630216]

题意

给n个人，每个人有k种爱好，[1,1000]的正整数代表不同爱好的编号。有部分相同爱好的人为一个集群。现在问这n个人一共组成了多少个集群，每个集群有多少人

题解

对于每个人的k个爱好，把这k个爱好用并查集merge成一坨，然后直接遍历并查集p[1-1000]就行。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF =0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline ll read();
int p[10005];
int find(int x){
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
int main() {
    int n;
    int a[10005]={0};
    for(int i=1;i<=1000;i++)p[i]=i;
    cin>>n;
    for(int i=1;i<=n;i++){
        int m;
        scanf("%d:",&m);
        int x;
        cin>>x;
        for(int j=1;j<=m-1;j++){
            int y;
            cin>>y;
            p[find(x)]=p[find(y)];
        }
        a[i]=p[find(x)];
    }
    int mp[10005]={0};
    for(int i=1;i<=1000;i++){
        mp[find(a[i])]++;
    }
    sort(mp+1,mp+1001);
    reverse(mp+1,mp+1001);
    int cnt=0;
    for(int i=1;i<=1000;i++){
        if(mp[i]>0)cnt++;
    }
    cout<<cnt<<'\n';
    int tag=1;
    for(int i=1;i<=1000;i++){
        if(mp[i]>0) {
            if (tag)cout << mp[i], tag = 0;
            else
                cout << ' ' << mp[i];
        }
    }
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
#define ll long long
const int N = 1005, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];
int d[N][N] ;// d[i][j]代表i到j点的路径上最大的一条边 (如果N较大可以用哈希表)
vector<int> path[N]; //扩展路径，path数组，缩写p
struct Edge {
    int a, b, w;
    bool vis;

    bool operator<(const Edge &W) const //重载运算符以便于能直接sort
    {
        return w < W.w;
    }
} edges[M];

int find(int x) //并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int component = 1;//连通分量数量
ll kruskal() {
    sort(edges, edges + m);

    for (int i = 1; i <= n; i++) {
        p[i] = i;
        path[i].push_back(i);
    }   // 初始化并查集和路径

    ll res = 0, cnt = 0;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if (a != b)//找到的祖宗不相等说明不连通
        {
            p[a] = b;
            edges[i].vis = true;//标记进去最小生成树的集合
            res += w;
            cnt++;
            for (auto j:path[a])
                for (auto k:path[b]) {
                    d[j][k] = d[k][j] = w; //d[i][j]代表i到j点的路径上最大的一条边(之前排过序,w是递增的)
                }
            for (auto j:path[a]) path[b].push_back(j); //合并路径,标记a能到b
        }

    }


    for (int i = 1; i <= n - 1; i++) {
        if (find(i) != find(i + 1)) { component++; }
    }
    if (component > 1)return -1;
    return res;
}

int main() {
    ll sum = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
        sum += w;
    }

    int ans = kruskal();
    int res=INF;
    for (int i = 0; i < m; i++)
        if (!edges[i].vis)  //枚举每条没加入最小生成树的集合
            res = min(res, ans + edges[i].w - d[edges[i].a][edges[i].b]);
    if (ans == -1)cout << "No MST\n" << component;
    else{
        if(res>ans)cout<<ans<<'\n'<<"Yes";
        else{
            cout<<ans<<'\n'<<"No";
        }
    }

    return 0;
}

PTA-最小生成树的唯一性

题意

给定一个带权无向图，如果是连通图，则至少存在一棵最小生成树，有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重，并且判断其是否唯一。

题解

通过求并查集数量可得联通集个数，通过求次小生成树和最小生成树比较可得最小生成树是否唯一。

E - Destruction

题意

给一个无向图,让你从中选出几个边,要求选出的边权总和最大并且剩下的图要是一个连通图.

题解

要选出的边权总和最大,那就是让剩下的连通图边权总和最小,我们可以很容易想到最小生成树.但直接跑最小生成树是不行的,因为它有负边权.而负边我们是肯定不会选的,所以我们只需要特判一下,只要我们在跑最小生成树只要碰到负边权我们就给把它放进图里.(这样虽然不是树了但可以保证我们得到正确的答案)

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
#define ll long long
const int N = 200010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge {
    int a, b, w;

    bool operator<(const Edge &W) const //重载运算符以便于能直接sort
    {
        return w < W.w;
    }
} edges[M];

int find(int x) //并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

ll kruskal() {
    sort(edges, edges + m);

    for (int i = 1; i <= n; i++) p[i] = i;    // 初始化并查集

    ll res = 0, cnt = 0;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)//找到的祖宗不相等说明不连通
        {
            p[a] = b;
            res += w;
            cnt++;
        }
        else {
            if (w < 0)res += w;
        }
    }

    return res;
}

int main() {
    ll sum = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
        sum += w;
    }

    cout << sum - kruskal();


    return 0;
}

搜索/树

DFS

图k-着色问题

题意

给定一个n顶点m条边的无向图，k(k<=n)种颜色，相邻两个顶点颜色不相同，问总共有多少种涂色方法

思路

dfs枚举

将颜色用数字1~k表示。一开始能想到从第一个顶点开始涂第1种颜色，然后和它相邻的顶点涂第2种颜色。以此类推。题目要求涂色的方法数目，所以从第一个点开始就枚举涂1~k种颜色。然后枚举下一个点，若下一个点和这个点相邻且颜色相同，那就不能继续搜。反之则可以（相邻颜色不同或者直接不相邻都能继续涂色方案）若枚举的点数超过n说明涂色完了，是一种方案，所以方案数+1。其中要注意涂了色之后要还原现场。

#include<iostream>
using namespace std;
int n,m,k;
int g[105][105];
int sum=0;//记录答案数量
int color[105];
int ok;
void dfs(int u){
    if(u>n) {
        sum++;
        return;
    }
    for(int i=1;i<=k;i++){
        color[u]=i;
        ok=1;
        for(int j=1;j<=n;j++){
            if(g[u][j]&&color[j]==color[u]){
                ok=0;
                break;
            }
        }
        if(ok)dfs(u+1);
        color[u]=0;
    }
}
int main(){
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a][b]=1;
        g[b][a]=1;

    }
    dfs(1);
    cout<<sum;
}

F - Distance Sums 2

题意

给你n个点n-1条边，然后依次求出每个点到其他所有点的距离和

思路

每次搜索计算该点的子节点数量

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PIII pair<int,PII>
#define PLLL <ll,PLL>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;
vector<ll> g[N];
ll dis[N], son_size[N];

void dfs(ll u, ll fa, ll d) {

    for (auto i: g[u]) {
        if (i == fa)continue;
        dis[1] += d + 1;//根节点到其他所有点的距离之和
        dfs(i, u, d + 1);
        son_size[u] += son_size[i];

    }
}

void dfs2(ll u, ll fa) {
    for (auto i: g[u]) {
        if (i == fa)continue;
        dis[i] = dis[u] - (son_size[i] - 1) + (n - son_size[i]-1);//每次从节点移动到其儿子,都可以通过这个节点到其他点的距离之和用该公式推出其儿子节点到其他点的距离之和
        dfs2(i, u);
    }
}

int main() {
    //ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)son_size[i] = 1;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, 1, 0);
    //cout << dis[1] << '\n';
    dfs2(1,1);
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << '\n';
    }

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

[NOI2011]道路修建

题意

给定一棵树,对于每一条边,对于答案的贡献为边长*abs(所连两点两边的点的个数差)

和上题类似,硬模拟

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PIII pair<int,PII>
#define PLLL <ll,PLL>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 1e6 + 5;
const int M = 1e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

ll n, m;
vector<PLL > g[N];
ll sz[N];

void dfs(ll u, ll fa) {
    for (auto i: g[u]) {
        if (i.se == fa)continue;
        dfs(i.se, u);
        sz[u] += sz[i.se];
    }
}

ll sum = 0;

void dfs2(ll u, ll fa) {
    //debug(sz[u]);
    for (auto i: g[u]) {
        if (i.se == fa)continue;
        sum += i.fi * abs(sz[i.se]  - (n-sz[i.se]));
        //cout<<u<<' '<<i.se<<' '<<sz[i.se]<<' '<<sz[u]-sz[i.se]<<'\n';
        dfs2(i.se, u);
    }
}

int main() {
    //ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)sz[i] = 1;
    for (int i = 0; i < n - 1; i++) {
        ll u, v, c;
        cin >> u >> v >> c;
        g[u].pb({c, v});
        g[v].pb({c, u});
    }
    dfs(1, 1);
    dfs2(1, 1);
    //for(int i=1;i<=n;i++)cout<<sz[i]<<'\n';
    cout << sum;
    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

J - Kingdom’s Power

贪心 先走深度浅的,最后走最深的.可以转化为对于当前父亲结点u所有不是最长的链都会走两次或者走一次+从根结点来一次,只有最长的链只用走一次

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PIII pair<int,PII>
#define PLLL pair<ll,PLL>
#define fi first
#define se second
#define pb push_back
//#define LOCAL
#define debug(a) cout << #a << " " << a << '\n';
const int N = 1e6 + 5;
const int M = 1e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

vector<int> g[N];
int n, m;
ll ans;

ll dfs(int u, ll dep) {
    ll ma = 0;
    for (auto i: g[u]) {
        ll t = dfs(i, dep + 1);//叶子结点到当前结点的距离
        ans += min(dep, t);//从根结点到当前结点,从叶子结点到当前结点,取一个最小值
        ma = max(ma, t);//2.ma遇到分支后将分支的所有链长取最大值,就是该分支下的最长链长	
    }
    ans -= min(ma, dep);//减掉最长的链重复走的
    return ma + 1;//1.ma没遇到分支时就相当于只是递归的求叶子结点到当前结点的距离
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++)g[i].clear();
    for (int i = 2; i <= n; i++) {
        int f = read();
        g[f].pb(i);
    }
    ans = n - 1;
    dfs(1, 0);
    cout << ans << '\n';
}

int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    T = read();
    for (int cas = 1; cas <= T; cas++) {

        printf("Case #%d: ", cas);
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

双端BFS

E - Stronger Takahashi

题意

从 走到 ，只能走在 . 上不能走在 # 上，每次可以消掉 2×2的 #，求最少消掉几次才能到终点。

思路

走#花费为1,然后可以以0的花费走以这个#为中心的2x2,就相当于花1的花费直接瞬移到这些位置.

走.是0的花费

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 505;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;
char g[N][N];
int dis[N][N];
bool st[N][N];

void bfs() {
    deque<PII > dq;
    memset(dis, 0x3f, sizeof dis);
    memset(st, 0, sizeof st);
    dis[0][0] = 0;
    dq.pb({0, 0});
    int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
    while (!dq.empty()) {
        auto t = dq.front();
        dq.pop_front();
        if (st[t.fi][t.se])continue;
        st[t.fi][t.se] = true;
        for (int i = 0; i < 4; i++) {
            int a = t.fi + dx[i], b = t.se + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m)continue;
            if (g[a][b] == '#') {
                for (int j = -1; j <= 1; j++) {
                    for (int k = -1; k <= 1; k++) {
                        int xx = a + j, yy = b + k;
                        if (xx < 0 || xx >= n || yy < 0 || yy >= m)continue;
                        if (dis[t.fi][t.se] + 1 < dis[xx][yy]) {
                            dis[xx][yy] = dis[t.fi][t.se] + 1;
                            dq.push_back({xx, yy});
                        }

                    }
                }
            }
            else {
                if (dis[t.fi][t.se] < dis[a][b]) {
                    dis[a][b] = dis[t.fi][t.se];
                    dq.push_front({a, b});
                }
            }

        }
    }

}

int main() {
    //ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }
    bfs();
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++)cout << dis[i][j] << " ";
//        cout << '\n';
//    }
    cout << dis[n - 1][m - 1];
    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

图论

求最短路的路径数

D - Number of Shortest paths

题意

n座城m条路，走每一条路的时间为1，问从City 1 到City n 的最短路有几条

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int dis[N];
bool st[N];
int n, m;
vector<int> g[N];
int minn[N];

void dijkstra() {
    priority_queue<PII, vector<PII >, greater<>> heap;
    memset(dis, 0x3f, sizeof dis);
    memset(st, false, sizeof st);
    dis[1] = 0;
    heap.push({0, 1});
    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.se, distance = t.fi;
        if (st[ver])continue;
        st[ver] = true;
        for (auto i: g[ver]) {
            if (dis[i] >= distance + 1) {
                if (dis[i] == distance + 1)minn[i] =(minn[i]+ minn[t.se])%mod;//记录条数
                else {
                    dis[i] = distance + 1;
                    minn[i]=minn[t.se];
                    //cout<<i<<' '<<minn[i]<<"\n";
                    heap.push({dis[i], i});
                }
            }
        }
    }
}


int main() {
    //ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    minn[1] = 1;
    dijkstra();

    cout << minn[n];

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

stl乱搞

优先队列乱搞

D - Querying Multiset

题意

有很多球和一个空的包，q次操作，每次可以操作三种操作其中之一：

第一种操作：在球上写下一个数字x并放入包中

第二种操作：让包中所有球的数字+x

第三种操作：选择包中数字最小的球取出，并记录该球的数字

输出第三种操作取出的球的数字。

思路

因为要选择最小数字的球取出，考虑优先队列。但在队列中第二种操作其实不方便操作，于是考虑对堆外的球进行反向操作，定义y为之前所有第二种操作的和，对之后的球上的数字减去一个y再放入包中（这样包中所有数字整体减小了y，其相对大小不变），在输出时补上y即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;
vector<PII > v[N];

int main() {
    //ios::sync_with_stdio(false);
    cin >> n;
    priority_queue<ll, vector<ll>, greater<>> heap;
    ll ans = 0;
    while (n--) {
        int op;
        cin >> op;
        if (op == 1) {
            ll x;
            cin >> x;
            heap.push(x - ans);
        }
        else if (op == 2) {
            ll x;
            cin >> x;
            ans += x;
        }
        else {
            cout << heap.top() + ans << '\n';
            heap.pop();
        }
    }

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

E - Sorting Queries

题意

三种操作：

1. 向A数组中加入X
2. 拿出A数组第一个元素，并输出
3. 对数组进行排序

思路

用优先队列来维护有序的数。我们要拿第一个元素，肯定先拿我们排序的那些数，如果优先队列为空，那么我们拿普通队列里的元素。如果需要排序，我们将普通中的元素放进优先队列即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 1e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;

int main() {
    //ios::sync_with_stdio(false);
    queue<int>q1;
    priority_queue<int,vector<int>,greater<>>q2;

    n = read();
    int d = 0;
    int len=0;
    while (n--) {
        int op, x;
        op = read();
        if (op == 1)x = read(), q1.push(x);
        else if (op == 2) {
            if(q2.empty())printf("%d\n",q1.front()),q1.pop();
            else{
                printf("%d\n",q2.top());
                q2.pop();
            }
        }
        else {
            while(!q1.empty())q2.push(q1.front()),q1.pop();
        }
    }

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

SET乱搞

D - Cutting Woods

题意

有一根长度为L的木头，这根木头上有L - 1个可以劈的点，对这根木头进行q次操作，操作有两种：操作一是往一个可劈点劈一刀，把这个点所在的木头段劈成两段；操作二是输出一个可劈点所在木头段的长度。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n;
int a[N], p[N];

int main() {
    //ios::sync_with_stdio(false);
    int q;
    set<int> s1;
    cin >> n >> q;
    s1.insert(0);
    for (int i = 0; i < q; i++) {
        int c, x;
        cin >> c >> x;
        if (c == 1)s1.insert(x);
        else {
            if (s1.size()==1)cout << n << '\n';
            else {
                int pos1 = n, pos2 = 0;
                auto t = s1.lower_bound(x);
                if (t != s1.end())pos1 = *t;
                //cout<<*t<<'\n';
                t--;
                //cout<<*t<<'\n';
                if (t != s1.begin())pos2 = *t;
                cout << pos1 - pos2 << '\n';
            }
        }
    }
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

大模拟

Texas hold’em Poker

模拟简化版的德州扑克

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#pragma GCC optimize(2)
using namespace std;
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N=1e5+5;
const int M=1e5;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const ll mod = 1e9 + 7;
int n,m;
int b[N][15];
string s[N];
struct stru{
    string name;
    int rank,d1,d2,res;
}a[N];
bool cmp(stru a,stru b){
    if(a.rank!=b.rank)return a.rank>b.rank;
    if(a.d1!=b.d1)return a.d1>b.d1;
    if(a.d2!=b.d2)return a.d2>b.d2;
    if(a.res!=b.res)return a.res>b.res;
    return a.name<b.name;
}
int ran=0,d1=0,d2=0,res=0;
void judge(int idx){
    if(b[idx][1]==1&&b[idx][10]==1&&b[idx][11]==1&&b[idx][12]==1&&b[idx][13]==1){
        ran=8;
        return;
    }
    for(int i=1;i+4<=13;i++){//顺
        if(b[idx][i]==b[idx][i+1]&&b[idx][i]==b[idx][i+2]&&b[idx][i]==b[idx][i+3]&&b[idx][i]==b[idx][i+4]&&b[idx][i]==1){
            ran=7;
            d1=i+4;
            return;
        }
    }
    for(int i=1;i<=13;i++){//葫芦
        if(b[idx][i]==4) {
            ran = 6;
            d1=i;
            for(int j=1;j<=13;j++){
                if(b[idx][j]==1) {
                    res = j;
                    return;
                }
            }
        }
    }
    vector<int>v;
    int cnt3=0,idx3=0;
    for(int i=1;i<=13;i++){
        if(b[idx][i]==3)cnt3++,idx3=i;
        else if(b[idx][i]==2)v.push_back(i);
    }
    if(cnt3==1&&v.size()==1){//全满
        ran=5;
        d1=idx3;
        d2=v[0];
        return;
    }
    int sum=0;
    for(int i=1;i<=13;i++){
        if(b[idx][i]==1)sum+=i;
    }
    if(cnt3==1&&v.size()==0){//三条
        ran=4;
        d1=idx3;
        res=sum;
        return;
    }
    if(v.size()==2){//两对
        ran=3;
        d1=max(v[0],v[1]);
        d2=min(v[0],v[1]);
        res=sum;
        return;
    }
    if(v.size()==1){//一对
        ran=2;
        d1=v[0];
        res=sum;
        return;
    }
    ran=1;
    res=sum;//高牌
    return;

}
int main(){


    ios::sync_with_stdio(false);
    while(cin>>n) {
        map<string, int> ori;
        for (int i = 0; i < n; ++i) {
            cin >> a[i].name >> s[i];
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < s[i].length(); j++) {
                if (j + 1 < s[i].length())
                    if (s[i][j] == '1' && s[i][j + 1] == '0') {
                        b[i][10]++;
                        j++;
                    }
                if (s[i][j] == 'A')b[i][1]++;
                else if (s[i][j] == 'J')b[i][11]++;
                else if (s[i][j] == 'Q')b[i][12]++;
                else if (s[i][j] == 'K')b[i][13]++;
                else {
                    b[i][s[i][j] - '0']++;
                }


            }
        }
        for (int i = 0; i < n; i++) {
            ran = 0, d1 = 0, d2 = 0, res = 0;
            judge(i);
            a[i].rank = ran;
            a[i].d1 = d1;
            a[i].d2 = d2;
            a[i].res = res;
            //cout<<a[i].name<<' '<<a[i].rank<<' '<<a[i].d1<<' '<<a[i].d2<<' '<<res<<'\n';
        }
        sort(a, a + n, cmp);
        for (int i = 0; i < n; ++i) {
            cout << a[i].name << '\n';
        }
    }
    return 0;
}

The 15th Chinese Northeast Collegiate Programming Contest M. Master of Shuangpin

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 5005;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;
vector<string> v[1005];//存输入
string ans[1005][1005];//存答案
bool st[1005][1005];//已经被操作过的串标记一下 以免重复操作
unordered_map<string, string> mp;

int main() {
    //ios::sync_with_stdio(false);
    mp["iu"] = "q", mp["en"] = "f", mp["ei"] = "w", mp["eng"] = "g";
    mp["ang"] = "h", mp["uan"] = "r", mp["an"] = "j", mp["ue"] = "t";
    mp["uai"] = "k", mp["ing"] = "k", mp["un"] = "y", mp["uang"] = "l";
    mp["iang"] = "l", mp["sh"] = "u", mp["ou"] = "z", mp["ch"] = "i";
    mp["ia"] = "x", mp["ua"] = "x", mp["uo"] = "o", mp["ao"] = "c";
    mp["ie"] = "p", mp["zh"] = "v", mp["ui"] = "v", mp["in"] = "b";
    mp["ong"] = "s", mp["iong"] = "s", mp["iao"] = "n", mp["ai"] = "d";
    mp["ian"] = "m";
    for (int i = 0; i < 26; i++) {
        string s;
        s += char('a' + 0);
        mp[s] = s;
    }
    string s;
    int d = 0;
    while (getline(cin, s)) { //处理输入
        //if(s=="0")break;
        string tmp;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ' ') {
                v[d].pb(tmp);
                tmp.clear();
            } else {
                tmp += s[i];
            }

        }
        v[d].pb(tmp);
        d++;
    }
    for (int i = 0; i < d ; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            if (v[i][j].size() == 1) { //只有一个字母的情况 直接复制 eg:a->aa b->bb...
                ans[i][j] = v[i][j];
                ans[i][j] += v[i][j];
                st[i][j] = true;
            } else if (v[i][j].size() == 2) {//两个字母的情况:不用做任何操作,答案直接是它本身
                ans[i][j] = v[i][j];
                st[i][j] = true;
            } else {
                for (auto t:mp) {//单独一个 例如ang之类的情况

                    if (t.fi == v[i][j]) {
                        ans[i][j] = t.fi[0];
                        ans[i][j] += t.se;
                        st[i][j] = true;
                    }
                }
            }
        }
    }

    for (int i = 0; i < d ; i++) {
        for (int j = 0; j < v[i].size(); j++) {//声母是单个的情况，除了声母以外一定能找到一个长度大于1的韵母
            if (!st[i][j] && mp.find(v[i][j].substr(1)) != mp.end()) {
                ans[i][j] = v[i][j][0];
                ans[i][j] += mp[v[i][j].substr(1)];
                st[i][j] = true;
            }
            if (!st[i][j] && mp.find(v[i][j].substr(0, 2)) != mp.end()) {//声母是两个的情况 例如ch sh
                ans[i][j] = mp[v[i][j].substr(0, 2)];
                if (v[i][j].size() <= 3) { //只剩下一个韵母 答案直接加上它
                    ans[i][j] += v[i][j][2];
                } else {
                    if (mp.find(v[i][j].substr(2)) != mp.end()) {//剩下两个韵母
                        ans[i][j] += mp[v[i][j].substr(2)];
                    }
                }
                st[i][j] = true;
            }
        }
    }
    for (int i = 0; i < d ; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            cout << ans[i][j] ;
            if(j<v[i].size()-1)cout<<' ';
        }
        if(i<d-1)puts("");
    }
    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

数学

矩阵快速幂

Matrix Power Series

给定矩阵A，求的结果（两个矩阵相加就是对应位置分别相加）。输出的数据。

#include<iostream>
#include<cstring>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF =0x3f3f3f3f3f3f3f3f;
inline ll read();
ll tot,tota;
struct mat {//定义矩阵结构体
    ll m[105][105];

    mat() {
        memset(m, 0, sizeof(m));
    }
};
ll n,k,mod;
mat operator*(mat a, mat b) {//定义矩阵乘法
    mat ans;
    ll x = 0;
    for (int i = 0; i < tot; i++) {
        for (int j = 0; j < tot; j++) {
            x = 0;
            for (int k = 0; k < tot; k++) {
                x = (x + a.m[i][k] * b.m[k][j])%mod;
            }
            ans.m[i][j] = x;
        }
    }
    return ans;
}

mat init(mat &a) {//初始化单位矩阵（按要求自定义）
    for (int i = 0; i < tot; i++) {
        for(int j=0;j<tot;j++){
            a.m[i][j]=0;
        }
    }
    for (int i = 0; i < tot; i++) {
        a.m[i][i] = 1;
    }
    return a;
}

mat mat_pow(mat a, ll k) {//矩阵快速幂
    mat ans = init(ans);
    while (k) {
        if (k & 1) ans = ans * a;
        a = a * a;
        k >>= 1;
    }
    return ans;
}

mat a;
void solve() {
    n=read();
    k=read();
    mod=read();
    tot=2*n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            a.m[i][j]=read();
            a.m[i+n][j]=a.m[i][j];
        }
    }
    mat bas;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            bas.m[i][i]=1;
            bas.m[i+n][j+n]=a.m[i][j];
            bas.m[i][j+n]=a.m[i][j];
            bas.m[i+n][j]=0;
        }
    }

    bas= mat_pow(bas,k-1);
    mat res=bas*a;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<((res.m[i][j])%mod+mod)%mod<<' ';
        }
        cout<<'\n';
    }
}
int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    //T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

高斯消元

Matrix Equation

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")

//define LOCAL
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PIII pair<int,PII>
#define PLLL pair<ll,PLL>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 205;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;

inline ll read();

int n, m;
int a[N][N];
int origin_a[N][N];
int b[N][N];
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
void init(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            a[i][j]=origin_a[i][j];
        }
    }
}
int gauss() {
    int c, r;
    for (c = 0, r = 0; c < n; c++) {
        int t = r;
        for (int i = r; i < n; i++)
            if (a[i][c])
                t = i;

        if (!a[t][c]) continue;

        for (int i = c; i < n + 1; i++) swap(a[r][i], a[t][i]);
        for (int i = r + 1; i < n; i++)//将下面所有行的第c列消成0
            if (a[i][c])
                for (int j = n; j >= c; j--)
                    a[i][j] ^= a[r][j];//该行第c列肯定是1，所以下面行异或该行第c列肯定可以消成0（两个1异或）

        r++;
    }

    if (r < n) {
        for (int i = r; i < n; i++)
            if (a[i][n])
                return -1;
        return n-r;
    }

    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            a[i][n] ^= a[i][j] & a[j][n];

    return 0;
}
void solve() {
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>origin_a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>b[i][j];
        }
    }
    ll ans=1;
    for(int i=0;i<n;i++){
        init();
        for(int j=0;j<n;j++){
            a[j][j]=(origin_a[j][j]-b[j][i]+2)%2;
        }
        int d=gauss();
        //debug(d)
        if(d==-1)continue;
        ans=(ans* qpow(2,d))%mod;

    }
    cout<<ans%mod;

}

int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    //T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

Acwing 207.球形空间产生器

给一个整数n和n+1行 表示一个n维球面上的n+1个n维坐标,求球心的坐标.

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF =0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline ll read();
int n;
double origin_a[15][15];
double a[15][15];
const double eps=1e-8;
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )//枚举每一列
    {
        int t = r;
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][c]) > fabs(a[t][c]))//找到绝对值最大的那一行
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]);//把绝对值最大的一行换到最上面
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];//把该行第一个数变成1->倒着更新,不然第一个数先被更新成1除后面的数就无效了

        for (int i = r + 1; i < n; i ++ )
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];//把下边所有行的第c列消成0

        r ++ ;
    }


    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )//倒着把其他系数全部消成0（解所在位置的系数是1）
            a[i][n] -= a[j][n] * a[i][j];

    return 0;//唯一解
}
void solve() {
    cin>>n;
    for(int i=0;i<n+1;i++)
        for(int j=0;j<n;j++)cin>>origin_a[i][j];
    for(int i=0;i<n;i++){
        double sum=0;
        for(int j=0;j<n;j++){
            a[i][j]=2.0*(origin_a[i+1][j]-origin_a[0][j]);
            sum+=origin_a[i+1][j]*origin_a[i+1][j]-origin_a[0][j]*origin_a[0][j];
        }
        a[i][n]=sum;
    }
    gauss();
    for(int i=0;i<n;i++){
        printf("%.3lf ",a[i][n]);
    }

}
int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    //T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

Acwing 208.开关问题

题意

思路

解集矩阵:第个开关初态和终态一样第行的解集矩阵就是0,不一样就是1

为1表示第个开关会对第个开关产生影响

最后解出自由元个数,说明这个开关可以是任意的状态,所以方案数为

2021 ICPC Asia Jinan Regional Contest J Determinant

题意

给你一个行列式以及行列式的值的绝对值(长度可能是)求这个行列式的值是正还是负

思路

先让大数模一个大素数(),然后求行列式取模的值,判断两个数相不相等,如果相等就是正数,不相等就是负数.

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int N = 105;
const ll mod = 1e9 + 7;

inline ll read();

ll A[N][N];

ll quick_pow(ll a, ll n) {
    ll ans = 1;
    while (n) {
        if (n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

ll inv(ll a) {
    return quick_pow(a, mod - 2);
}

ll gauss(int n) {
    ll ans = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (A[j][i]) {
                for (int k = i; k <= n; k++) swap(A[i][k], A[j][k]);
                if (i != j) ans = -ans;
                break;
            }
        }
        if (!A[i][i]) return 0;
        for (ll j = i + 1, iv = inv(A[i][i]); j <= n; j++) {
            ll t = A[j][i] * iv % mod;
            for (int k = i; k <= n; k++)
                A[j][k] = (A[j][k] - t * A[i][k] % mod + mod) % mod;
        }
        ans = (ans * A[i][i] % mod + mod) % mod;
    }
    return ans;
}

int n;
string s;
void solve() {
    cin >> n;
    cin >> s;
    int len = s.length();
    ll ans = s[0] - '0';
    for (int i = 1; i <len; i++) {
        ans = ((ans * 10)%mod + (s[i] - '0')) % mod;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> A[i][j];
        }
    }
    ll res = gauss(n);
//    debug(res)
//    debug(ans)
    if (res == ans)cout << '+' << '\n';
    else {
        cout << '-' << '\n';
    }

}

int main() {
    ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

二分/三分

三分

P1883 函数

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF =0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const double eps=1e-9;
inline ll read();
int n;
double a[10005],b[10005],c[10005];
double f(double x){
    double ans=0;
    for(int i =0;i<n;i++){
        ans=max(ans,a[i]*x*x+b[i]*x+c[i]);
    }
    return ans;
}
void solve() {
    n=read();
    for(int i=0;i<n;i++) {
        a[i]=read();
        b[i]=read();
        c[i]=read();
    }
    double l = 0,r = 1000;
    while(r-l>=eps){//精度问题
        double m1 = l + (r-l)/3.0,m2 = r - (r-l)/3.0;
        if(f(m1)<f(m2))
            r = m2;
        else
            l = m1;
    }
   printf("%.4lf\n",f(l));

}
int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

2020ICPC南京 F.Fireworks

题意

给定n，m，p，制作一个烟花需要花费n分钟，点燃的时候只有p/1e4的概率可以制作成真烟花，在做完一个烟花后，你可以花费m分钟一次性点燃之前所有烟花，如果至少有一个烟花成功释放，那么结束，否则继续，问如果采用最优策略，结束的最小期望时间。

思路

设p为制作成功的概率 设为制作失败的概率 设最优解情况下是制作个之后点燃, 如果释放成功那么结束，如果释放失败那么下一次还是制作k个， 期望时间为 现在要找到最小的,容易推测出是单峰函数， 因此三分即可.

• 注意调精度

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF =0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline ll read();
double n,m,p;
ll qpow(ll a,ll k){
    ll res=1;
    while(k){
        if(k&1)res*=a;
        k>>=1;
        a*=a;
    }
    return res;
}
double f(ll x){
    return (n*(double)x+m)/(1.0- pow(1.0-p,(double)x));
}
void solve() {
    cin>>n>>m>>p;
    p/=10000.0;
    int l=0,r=1e9;
   // cout<<f(1)<<'\n';
    while(r-l>=10){
        int m1=l+(r-l)/3,m2=r-(r-l)/3;
        if(f(m1)<f(m2)){
            r=m2;
        }
        else
            l=m1;
    }
    double ans=LLINF;
    for(int i=l;i<=r;i++){
        ans=min(ans,f(i));
    }
    printf("%.10lf\n",ans);


}
int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    cin>>T;
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

二分

P1843 奶牛晒衣服

• 注意这里烘干机的最小使用单位是1s,题目没说

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

const int N = 5e5 + 5;
int n, a, b;
int w[N];

bool check(int x) {
    ll cha = 0, cnt = x;
    int flag = 0;
    for (int i = 1; i <= n; i++) {
        if (w[i] > x * a) {
            cha = w[i] - x * a;
            cnt -= (cha + b - 1) / b;

        }
    }
    if (cnt>=0)return true;
    else {
        return false;
    }
}

void solve() {
    cin >> n >> a >> b;
    int ma = -1;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        ma = max(ma, w[i]);
    }
    ma = (ma + a - 1) / a;
    int l = 1, r = ma, mid;
    while (l < r) {
        mid = l + r >> 1;
        if (check(mid))r = mid;
        else
            l = mid + 1;
    }
    cout << l;


}

int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    // T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

G - Occupy the Cities

题意

给一个01字符串，1代表被占领。每一轮所有的1可以向把相邻的其中一个变成1，问至少多少轮后可以使所有位置都是1。

思路

因为轮数最少是0最多是串长减1，所以考虑二分轮数。check函数有一些细节：在中间的1，可以先向右扩展一个1（eg：00110）或者先向左边扩展一个1（eg：01100）然后两边一起扩展。假设二分的答案为x，如果对于一个最左边的1，这个1左边的0的个数都大于x了，那肯定是return false。但如果正好等于x的话，那就只能考虑先把左边扩展一个1，然后两边一起扩展的情况。如果大于x，那就可以先向右边扩展一个1，再向两边一起扩展。简单来说就是两种情况：1.左边扩x-1，右边扩x 2.左边扩x，右边扩x-1。

#include<bits/stdc++.h>

#define ll long long
using namespace std;
const ll maxn = 1e6 + 7;
const ll N = 5e6 + 7;
int n;
vector<int> a;
char s[maxn];

bool check(int x) {
    int now = 0;
    int sz = a.size();
    for (int i = 0; i < sz - 1; i++) {
        if (now + x + 1 < a[i])return false;
        if (now + x >= a[i]) {
            now = a[i] + x;
        }
        else {
            now = max(a[i], a[i] + x - 1);//取max是防止当x为0时，now反而还减小的情况
        }
        if (now >= a[i + 1]) {//如果能扩的比右边那个1的位置还大，那就把now置为正好把a[i]~a[i+1]整段扩完
            now = a[i + 1] - 1;
        }
    }
    if (now == n) {
        return true;
    }
    return false;
}

void solve() {
    scanf("%d", &n);
    a.clear();
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        if (s[i] == '1') {
            a.push_back(i + 1);
        }
    }
    a.push_back(n + 1);
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    printf("%d\n", l);
}

int main() {
    int t = 1;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}

第k个数

题意

给出一个矩阵，每一个位置上的数，把这些数按照非严格单调递增的顺序，问第k大的数是多少。()

思路

是1e10的，考虑二分。每次二分一个数x，check小于等于x的数有多少个，如果个数大于等于x返回true（因为可能有超过1个数是等于x的，那其实也是符合要求的），然后发现第i行小于等于x的数就是,所以可以直接，算出来时间复杂度就是

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

ll n, m, k;

bool check(ll x) {
    ll res = 0;
    for (ll i = 1; i <= n; i++) {
        ll a = x / i;
        res += min(a,m);
    }
    //debug(res);
    if (res >= k)return true;
    else {
        return false;
    }
}

void solve() {

    cin >> n >> m >> k;
    ll l = 1, r = n * m, mid;
    while (l < r) {
        mid = l + r  >> 1;
        //(mid);
        if (check(mid))r= mid;
        else
            l=mid+1;
    }
    cout <<l;
}

int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    // T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        //printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

P1182 数列分段 Section II

题意

对于给定的一个长度为N的正整数数列 ，现要将其分成段，并要求每段连续，且每段和的最大值最小。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 1e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;
ll a[N];

inline bool check(ll x) {
    ll sum = 0, cnt = 1;
    for (int i = 0; i < n; i++) {
        if (sum + a[i] <= x)sum += a[i];//划分的每一段不能超过x
        else sum = a[i], cnt++;
    }
    return cnt <= m;//如果划分的每一段都不超过mid并且分的段数还小于m说明可以继续分
}

int main() {
    //ios::sync_with_stdio(false);
    ll l = -1, r = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        l = max(l, a[i]);//注意二分的范围
        r += a[i];
    }
    //cout<<l<<' '<<r<<'\n';
    while (l < r) {
        ll mid = l + r >> 1;
        //cout << mid << '\n';
        if (check(mid))r = mid;//要继续分所以减小mid

        else {
            l = mid + 1;//分得段太多,说明答案还可以继续增大
        }
    }
    cout << l;

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

ABC216 E Amusement Park

题意:

给N个点,K次访问,每个点有一个值,每个点可以访问无限次,每次访问就可以获得其值,但每访问一次这个点的值就会减1.最大化K次访问后值的总和.

做法1:(思维+模拟)

我们都可以想到要优先取最大的值,所以第一步是将数组从大到小排序,但我们不能一直取最大的那个值,因为它是随着取得次数减小的.所以我们能想到把最大的数取到和第二大的数一样,然后再取第二大的数,将其取到和第三个大的数一样.

eg.
10 9 5 4 3 -> 9 9 5 4 3 -> 5 5 5 4 3 -> 4 4 4 4 3 -> 3 3 3 3 3

我们可以找到规律:第i大的数 可以被取i次

此时我们再结合等差数列的公式就可以算出答案.

细节部分会在代码中注释出来

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PLLL pair<ull,PLL>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
#define ull unsigned long long

inline ll read();

ll n, m, k;
PLL a[N];//a[i].first存值, a[i].second存从大到小排序后当前数和后一个数的差值

int main() {
    //ios::sync._with_stdio(false);
    n = read(), k = read();
    ll ans = 0;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        a[i].fi = read();
        ans += a[i].fi;
    }
    if (k >= ans) {//如果k比所有数字加起来都大,那直接计算所有数字1~a[i]的和
        for (int i = 0; i < n; i++) {
            sum += (a[i].fi + 1) * a[i].fi / 2;//等差数列求和公式
        }
    } else {
        sort(a, a + n);
        reverse(a, a + n);
        for (int i = 0; i < n - 1; i++) {
            a[i].se = (a[i].fi - a[i + 1].fi);
        }
        a[n - 1].se = a[n - 1].fi;

        for (int i = 0; i < n; i++) {
            if (a[i].se * (i + 1) < k) {//第i大的数有i个
                k -= a[i].se * (i + 1);//全部用完
                sum += (a[i].se * a[i].fi - (a[i].se * (a[i].se - 1)) / 2) * (i + 1);
                //cout << sum << '\n';
            } else {
                ll t = k / (i + 1);
                ll left = k % (i + 1);//这i个数同时等差数列求和到最后不一定都能用完
               // cout<<a[i].fi<<'\n';
                sum += (a[i].fi * t - t * (t - 1) / 2) * (i + 1);
                sum += left * (a[i].fi - t);
                k = 0;
            }

            if (k == 0)break;
        }
    }
    cout << sum;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

做法2:(二分)

先找出所有数的最大值,直接二分答案.check函数里判断当前比mid大的数和mid的差值的和是否大于k,如果大于说明mid值取小了,如果小于说明mid值取大了.

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

ll n, m, k;
ll a[N];

bool check(ll mid) {
    ll ans = 0;
    for (int i = 0; i < n; 
    i++) {
        if (a[i] > mid)ans += a[i] - mid;
    }
    return ans<=k;
}

int main() {
    //ios::sync_with_stdio(false);
    cin >> n >> k;
    ll maxx = -1;
    for (int i = 0; i < n; i++)cin >> a[i], maxx = max(maxx, a[i]);
    ll l = 0, r = maxx;
    ll mid;
    while (l < r) {
        mid = l + r >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    ll ans = 0;
    sort(a, a + n);
    reverse(a, a + n);
    //cout << l << ' ' << r << '\n';
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > l) {
            ans += (a[i] + l) * (a[i] - l + 1) / 2;
            cnt += a[i] - l + 1;
        }
    }
    ans -= (cnt - k) * l;//把多算的减掉
    cout << ans;


    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}
/*
5 10
10 9 5 4 3
 */

ABC192-D Base n

题意

给定一个字符串，由‘0’~‘9’组成，设是中最大的数字，求有多少个不同的整数，整数有以下要求：

• 是一个n进制数
• 这个数的n进制表示是
• n进制对应的十进制数

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 1e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

ll n, m;
string s;

bool check(__int128 mid) {
    __int128 ans = 0;
    for (__int128 i = s.length() - 1, j = 1; i >= 0; i--, j *= mid) {
        if (j > m)return false;
        ans +=  (s[i] - '0') * j;
        if (ans > m)return false;
    }
    if (ans <= m)return true;
    else
        return false;
}

int main() {
    //ios::sync_with_stdio(false);

    cin >> s >> m;
    int d = -1;
    for (auto i: s) {
        d = max(d, (i - '0'));
    }
    if (s.length() == 1) {
        if (s[0] - '0' <= m) {
            cout << 1;
        } else {
            cout << 0;
        }
    } else {
        ll l = d + 1, r = m;
        while (l < r) {
            //cout << l << ' ' << r << '\n';
            ll mid = l + r + 1 >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }

        }
        //cout << l << ' ' << r << '\n';
        if (check(l))cout << l - d;
        else {
            cout << 0;
            
        }

    }
    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

https://atcoder.jp/contests/abc215/tasks/abc215_f (二分+双指针+贪心)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;
PLL a[N];

bool check(ll mid) {
    ll miny = INF, maxy = -1;
    for (int i = 0, j = 0; i < n; i++) {
        while (j < i && a[i].fi - a[j].fi >= mid) {//a[i].fe因为排序了所以差值肯定是递增的
            miny = min(miny, a[j].se);
            maxy = max(maxy, a[j].se);
            j++;
        }
        if (maxy != -1 && miny != INF && (abs(a[i].se - miny) >= mid || abs(a[i].se - maxy) >= mid))return true;
    }
    return false;
}

int main() {
    //ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].fi >> a[i].se;
    }
    sort(a, a + n);
    ll l = 0, r = 1e9;
    while (l < r) {
        ll mid = l + r + 1 >> 1;

       // cout << mid << '\n';
        if (check(mid))l = mid;
        else {
            r = mid - 1;
        }
    }
    cout<<l;

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

字符串

后缀自动机/后缀数组

String Problem

求给定字符串的所有前缀中最长的字典序最大的串

后缀自动机做法：

用一个pos记录后缀自动机中的节点对应原串中节点的位置，然后直接从’z’到’a’贪心的在后缀自动机上dfs，第一次搜到的肯定是字典序最大的，记录其映射在原串上的位置以及深度即可得到答案。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 2000010;
int tot = 1, last = 1;
struct Node {
    int len, fa;
    int ch[26];
} node[N];
char str[N];
LL f[N];
int h[N], e[N], ne[N], idx;
int pos[N];//记录后缀自动机中的节点对应原串中节点的位置
int vis[N];
int ans[N];

//对于节点u的子串集合 最长的是node[u].len ,最短的是node[node[u].fa].len+1
void extend(int c, int id) {
    //fa：fail数组 ch：trie树 len:这个节点集合中字符串最长长度
    int p = last, np = last = ++tot;//np：初步建立的后缀自动机
    pos[np] = id;
    f[tot] = 1;//记录每个子串出现的次数
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1) node[np].fa = q;
        else {
            int nq = ++tot;//nq：当某节点没有合适的点做Fail的父亲时，需要的添加公共节点
            pos[nq] = pos[q];//!!!!注意这里也要标记
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int dept) {
    vis[u] = 1;
    for (int i = 25; i >= 0; i--) {//直接硬搜
        if (node[u].ch[i] && !vis[node[u].ch[i]]) {
            dfs(node[u].ch[i], dept + 1);
        }
    }
    if (!ans[pos[u]])ans[pos[u]] = pos[u] - dept + 1;//搜到底了，因为是从'z'到'a'搜，第一次搜到的一定是字典序最大的。
}

int main() {
    scanf("%s", str);
    for (int i = 0; str[i]; i++) extend(str[i] - 'a', i+1);
    memset(h, -1, sizeof h);
    dfs(1, 0);
    for (int i = 0; str[i]; i++)printf("%d %d\n", ans[i+1], i + 1);

    return 0;
}

后缀数组做法：

从后往前枚举Sa数组（字典序排名从大到小），对于当前，在之后的答案（并且小于上一个排名处理的有边界）对应一定是该排名的后缀，如果前一个sa数组的位置在当前的后面，就不用管，一直找到在当前前面为止，如果就说明其实如果继续往前取还能取到更长的并且字典序排名不小于的后缀，所以继续往前找

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

const int N = 1000010;
int n, m;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];
int ans[N];

void get_sa() {
    for (int i = 1; i <= n; i++) c[x[i] = s[i]]++;
    for (int i = 2; i <= m; i++) c[i] += c[i - 1];
    for (int i = n; i; i--) sa[c[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int num = 0;
        for (int i = n - k + 1; i <= n; i++) y[++num] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                y[++num] = sa[i] - k;
        for (int i = 1; i <= m; i++) c[i] = 0;
        for (int i = 1; i <= n; i++) c[x[i]]++;
        for (int i = 2; i <= m; i++) c[i] += c[i - 1];
        for (int i = n; i; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i++)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
        if (num == n) break;
        m = num;
    }
}

void get_height() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; i++) {
        if (rk[i] == 1) continue;
        if (k) k--;
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
        height[rk[i]] = k;
    }
}

void solve() {
    scanf("%s", s + 1);
    n = strlen(s + 1), m = 'z';
    get_sa();
    get_height();
    int r=n;
    for(int i=n;i>=1;i--)
    {
        int st=sa[i];
        int pos=i-1;
        while(sa[pos]>=sa[i])height[i]=min(height[i],height[pos]),pos--;
        if(st+height[i]>r)continue;
        for(int j=st+height[i];j<=r;j++)ans[j]=sa[i];
        r=st+height[i]-1;
        i=pos+1;
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<' '<<i<<'\n';
    }
}

int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    // T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

exkmp

D - Period

题意

给一个1e6的字符串，1e6个询问：把第x个位置的字符换成‘#’，字符串有多少个不同的周期？

如字符串长度为4 就有循环节长度为1，2，3种周期。

思路

要求这个串循环节为的周期，其实就是看有多少前缀与后缀相等。

对原串本身求exkmp，得到其每个后缀和原串能匹配的最长前缀的长度，如果这个长度等于该后缀的长度，那就说明这是一个循环。找到所有这样的循环把对应的前缀的位置上打上标记，说明到这里能有一个循环，然后做前缀和，就能快速查询到串中任意前缀能有多少个循环。把x位置替换成#，这时候的周期数就是（注意x=1时要特判，因为如果把第一个位置换成#之后不可能有周期与其匹配。）为什么是要是因为#对串的影响是让到这个#的周期全部失效，所以要找最小值。

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF =0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline ll read();
const int N=1e6+5;
char s[N];
char p[N];
int nxt[N];//p[i]...p[m - 1]与T的最长相同前缀长度
int extend[N];
int n;//s的长
int m;//p的长
int pre[N];
int tag[N];
void GetNext()
{
    int a = 0, pos = 0;
    nxt[0] = m;

    for (int i = 1; i < m; i++)
    {
        if (i >= pos || i + nxt[i - a] >= pos)
        {
            if (i >= pos)
                pos = i;

            while (pos < m && p[pos] == p[pos - i])
                pos++;

            nxt[i] = pos - i;
            a = i;
        }
        else
            nxt[i] = nxt[i - a];
    }
}

/* 求解 extend[] */
void GetExtend()
{
    int a = 0, pos = 0;
    GetNext();

    for (int i = 0; i < n; i++)
    {
        if (i >= pos || i + nxt[i - a] >= pos) // i >= p 的作用：举个典型例子，s 和 p 无一字符相同
        {
            if (i >= pos)
                pos = i;

            while (pos < n && pos - i < m && s[pos] == p[pos - i])
                pos++;

            extend[i] = pos - i;
            a = i;
        }
        else
            extend[i] = nxt[i - a];
    }
}
void solve() {
    scanf("%s",s);
    n=strlen(s);
    strcpy(p,s);
    m=n;
    GetExtend();
    //for(int i=0;i<n;i++)cout<<extend[i]<<' ';
    //cout<<'\n';
    for(int i=n-1;i>=0;i--){
        if(extend[i]==n-i)tag[n-i]=1;
    }
    //for(int i=0;i<n;i++)cout<<tag[i]<<' ';
    //cout<<'\n';
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+tag[i];
    //for(int i=0;i<n;i++)cout<<pre[i]<<' ';
    int q;
    scanf("%d",&q);
    while(q--){
        int x;
        scanf("%d",&x);
        //cout<<min(x-1,n-x)<<'\n';
        cout<<pre[min(x-1,n-x)]<<'\n';
    }
}
int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
   // T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

前缀和/差分

离散化+差分

Acwing1987.粉刷栅栏

题意

输入n个指令，每个指令代表从当前点向左或向右染色x个区间（从0点开始），问最后有多少区间被染色超过两次。

6
2 R
6 L
1 R
8 L
1 R
2 R

题解

先要进行转换，因为差分是对点进行操作，我们就把0看作代表区间，1代表区间。

然后用map离散化，然后根据差分数组求原数组，注意这里因为数据范围太大不能把原数组每个位置的值求出来，只能得到区间端点的值，然后就用一个类似于双指针的方法求，具体看代码。

代码

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

map<int, int> mp, sum;

void cha(int l, int r, int v) {
    mp[l] += v;
    mp[r + 1] -= v;
}

void solve() {
    int n;
    cin >> n;
    int last = 0;
    //0代表（0，1）区间，1代表（1，2）区间
    for (int i = 1; i <= n; i++) {
        int x;
        char direction;
        cin >> x >> direction;

        if (direction == 'R') {
            cha(last, last + x - 1, 1);
            //cout<<last<<' '<<last+x<<'\n';
            last = last + x;
        }
        else {
            cha(last - x, last - 1, 1);
            //cout<<last-x+1<<' '<<last<<'\n';
            last = last - x;
        }
        //cout<<x<<' '<<direction<<'\n';

    }
    int cnt = 0;
    int flag = 0;
    for (auto i: mp) {
        if (flag == 0) {
            flag = 1;
            sum[i.fi] += mp[i.fi];
            continue;
        }
        sum[i.fi] = sum[i.fi - 1] + mp[i.fi];
    }

    int ans = 0;
    int l = mp.begin()->fi, r = mp.begin()->fi;
    for (auto i: mp) {

        if (ans <= 1 && ans + i.se > 1) {
            l = i.fi;//找到满足条件的区间的左端点
        }
        else if (ans > 1 && ans + i.se <= 1) {
            r = i.fi;//找到满足条件的区间的右端点
            cnt += r - l;//值
        }
        ans += i.se;
    }
    cout << cnt;
}

int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    // T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}