2023 Xian Jiaotong University Programming Contest

A.大水题

#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fi first
#define se second
#define lc u << 1
#define rc u << 1 | 1
// #define int long long

// #define double long long
// #define int __int128_t
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e7 + 10;

// const int R = 999997;
const int Base = N / 2;
const int M = 1e6 + 10;

// const int P = 1 << 10;
const int INF = 2147483647;

typedef unsigned long long ULL;

const double eps = 1e-4;
const double PI = acos(-1);
const int mod = 1e9 + 7;
int n, k;
int d;
int m;
int Q;
int target;
// int p = INF;
// __int128_t a = 1;

// rope<int> r;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
int primes[N];
bool st[N];
int phi[N];
int cnt;
int T = 0;
LL s[N];

void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            st[i] = true;
            phi[i] = i - 1;
            primes[cnt++] = i;
        }
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[i * primes[j]] = true;
            if (i % primes[j])
            {
                phi[i * primes[j]] = phi[i] * phi[primes[j]];
            }
            else
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + phi[i];
    }
}

void solve()
{
    scanf("%d",&n);
    if(n <= 6)
    {
        printf("water\n");
    }
    else
    {
        printf("dry\n");
    }
}

signed main()
{
    int t = 1;
    // str = "codeforces";
    // init();
    // cout << cnt << endl;
    // init();
    // scanf("%d", &t);
    // getchar();
    // int a = 1;
    // for (int i = 1; i <= 26; i++)
    // {
    //     a = (a << 1) + 1;
    // }
    // cout << a << endl;
    // float t = 134217727;
    // int cnt = 200;
    // printf("%.16lf", t);
    // while (cnt--)
    // {
    //     t = t * 2 + a;
    //     printf("%.16f\n", t);
    // }
    // getchar();
    // cout << (int)(log(4) / log(2)) << endl;
    while (t--)
    {
        //     cout << t << endl;
        //     // cout << (2563 % 11) << endl;
        //     // cout << t << endl;
        solve();
        //     // cout << (((float)1) << 63) << endl;
        //     // cout << '\0' << endl;
        //     // cout << f(4);
        //     // cout<<(25 >> 5)
        //     // cout << gcd(31415, 14142);//
        //     // cout << (28284 / 11) << endl;
    }
    return 0;
}

/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *                               神兽保佑            永无BUG
 */

/**
 *  ┏┓   ┏┓+ +
 * ┏┛┻━━━┛┻┓ + +
 * ┃       ┃
 * ┃   ━   ┃ ++ + + +
 *  ████━████+
 *  ◥██◤ ◥██◤ +
 * ┃   ┻   ┃
 * ┃       ┃ + +
 * ┗━┓   ┏━┛
 *   ┃   ┃ + + + +Code is far away from  
 *   ┃   ┃ + bug with the animal protecting
 *   ┃    ┗━━━┓ 神兽保佑,代码无bug 
 *   ┃        ┣┓
 *    ┃        ┏┛
 *     ┗┓┓┏━┳┓┏┛ + + + +
 *    ┃┫┫ ┃┫┫
 *    ┗┻┛ ┗┻┛+ + + +
 */
View Code

B.原粥率

#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fi first
#define se second
#define lc u << 1
#define rc u << 1 | 1
// #define int long long

// #define double long long
// #define int __int128_t
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e7 + 10;

// const int R = 999997;
const int Base = N / 2;
const int M = 1e6 + 10;

// const int P = 1 << 10;
const int INF = 2147483647;

typedef unsigned long long ULL;

const double eps = 1e-4;
const double PI = acos(-1);
const int mod = 1e9 + 7;
int n, k;
int d;
int m;
int Q;
int target;
// int p = INF;
// __int128_t a = 1;

// rope<int> r;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
int primes[N];
bool st[N];
int phi[N];
int cnt;
int T = 0;
LL s[N];

void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            st[i] = true;
            phi[i] = i - 1;
            primes[cnt++] = i;
        }
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[i * primes[j]] = true;
            if (i % primes[j])
            {
                phi[i * primes[j]] = phi[i] * phi[primes[j]];
            }
            else
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + phi[i];
    }
}

void solve()
{
    double a, b;
    scanf("%lf %lf", &a, &b);
    printf("%.9lf\n", a / b);
}

signed main()
{
    int t = 1;
    // str = "codeforces";
    // init();
    // cout << cnt << endl;
    // init();
    // scanf("%d", &t);
    // getchar();
    // int a = 1;
    // for (int i = 1; i <= 26; i++)
    // {
    //     a = (a << 1) + 1;
    // }
    // cout << a << endl;
    // float t = 134217727;
    // int cnt = 200;
    // printf("%.16lf", t);
    // while (cnt--)
    // {
    //     t = t * 2 + a;
    //     printf("%.16f\n", t);
    // }
    // getchar();
    // cout << (int)(log(4) / log(2)) << endl;
    while (t--)
    {
        //     cout << t << endl;
        //     // cout << (2563 % 11) << endl;
        //     // cout << t << endl;
        solve();
        //     // cout << (((float)1) << 63) << endl;
        //     // cout << '\0' << endl;
        //     // cout << f(4);
        //     // cout<<(25 >> 5)
        //     // cout << gcd(31415, 14142);//
        //     // cout << (28284 / 11) << endl;
    }
    return 0;
}

/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *                               神兽保佑            永无BUG
 */

/**
 *  ┏┓   ┏┓+ +
 * ┏┛┻━━━┛┻┓ + +
 * ┃       ┃
 * ┃   ━   ┃ ++ + + +
 *  ████━████+
 *  ◥██◤ ◥██◤ +
 * ┃   ┻   ┃
 * ┃       ┃ + +
 * ┗━┓   ┏━┛
 *   ┃   ┃ + + + +Code is far away from  
 *   ┃   ┃ + bug with the animal protecting
 *   ┃    ┗━━━┓ 神兽保佑,代码无bug 
 *   ┃        ┣┓
 *    ┃        ┏┛
 *     ┗┓┓┏━┳┓┏┛ + + + +
 *    ┃┫┫ ┃┫┫
 *    ┗┻┛ ┗┻┛+ + + +
 */
View Code

C.话剧

#include<bits/stdc++.h>
using namespace std;

double x,y,z;

signed main()
{
    cin>>x>>y>>z;
    printf("%.6lf",z/(x*y));
}
View Code

D.点集扩张

#include<bits/stdc++.h>
using namespace std;

const int N=110,M=410;
bool st[M][M];
int n,x,y;

signed main()
{
    cin>>n;
    
    int x1=-0x3f3f3f3f,x2=0x3f3f3f3f,y1=-0x3f3f3f3f,y2=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        st[x+N][y+N]=true;
        x1=max(x1,x),x2=min(x2,x),y1=max(y1,y),y2=min(y2,y);
    }
    
    if(x2<=0&&x1>=0&&y2<=0&&0<=y1)
    {
        bool flag=true;
        for(int i=x2+N;i<=x1+N;i++)
            for(int j=y2+N;j<=y1+N;j++)
                if(!st[i][j]) flag=false;
        
        if(flag) cout<<x1-x2+y1-y2;
        else cout<<-1; 
    }else cout<<-1;
}
View Code

E.全错

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second

typedef pair<double,int> PDI;
const double esp=1e-6;
const int N=210;
bool dist[N][N];
int t,n;
string s;
double b;

int cmp(double a,double b)
{
    if(fabs(a-b)<esp) return 0;
    else if(a<b) return -1;
    return 1;
}

double init()
{
    double a;
    if(s[0]=='+') sscanf(s.c_str(),"+%lf",&a);
    else if(s[0]=='-') sscanf(s.c_str(),"-%lf",&a),a=-a;
    else sscanf(s.c_str(),"%lf",&a);
    
    return a;
}

signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>s;
        b=init();
        
        memset(dist,false,sizeof dist);
        
        PDI p[n];
        for(int i=1;i<=n;i++)
        {
            int idx=0;
            for(int j=1;j<=n;j++)
            {
                cin>>s;
                if(i==j) continue;
                double a=init();
                p[idx++]={a,j};
            }
            sort(p,p+idx,greater<PDI>());
            if(cmp(p[0].x,b)>=0) dist[i][p[0].y]=true;
        }
        if(n==1)
        {
            cout<<"kono jinsei, imi ga nai!"<<endl;
            continue;
        }
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                {
                    dist[i][j]=dist[i][j];
                    if(dist[i][k]&&dist[k][j]) dist[i][j]=true;     
                }
        bool flag=true;
        for(int i=1;i<=n;i++)
            if(!dist[i][i]) flag=false;
        
        if(flag) cout<<"wish you the best in your search"<<endl;
        else cout<<"hbxql"<<endl;        
    }
}
View Code

F.渡渡鸟游乐场

#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fi first
#define se second
#define lc u << 1
#define rc u << 1 | 1
// #define int long long

// #define double long long
// #define int __int128_t
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e7 + 10;

// const int R = 999997;
const int Base = N / 2;
const int M = 1e6 + 10;

// const int P = 1 << 10;
const int INF = 2147483647;

typedef unsigned long long ULL;

const double eps = 1e-4;
const double PI = acos(-1);
const int mod = 1e9 + 7;
int n, k;
int d;
int m;
int Q;
int target;
// int p = INF;
// __int128_t a = 1;

// rope<int> r;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
char s[1010];

void solve()
{
    scanf("%d", &n);
    m = 3 * n - 3;
    vector<vector<bool>> v(n + 1, vector<bool>(4));
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a][b] = true;
        bool f = false;
        if (b == 2)
        {
            if (v[a][1] || v[a][3])
            {
                if (i & 1)
                {
                    printf("Nocriz");
                    break;
                }
                else
                {
                    printf("Sheauhaw");
                    break;
                }
            }
        }
        else
        {
            if (v[a][2])
            {
                if (i & 1)
                {
                    printf("Nocriz");
                    break;
                }
                else
                {
                    printf("Sheauhaw");
                    break;
                }
            }
        }
    }
}

signed main()
{
    int t = 1;
    // str = "codeforces";
    // init();
    // cout << cnt << endl;
    // init();
    // scanf("%d", &t);
    // getchar();
    // int a = 1;
    // for (int i = 1; i <= 26; i++)
    // {
    //     a = (a << 1) + 1;
    // }
    // cout << a << endl;
    // float t = 134217727;
    // int cnt = 200;
    // printf("%.16lf", t);
    // while (cnt--)
    // {
    //     t = t * 2 + a;
    //     printf("%.16f\n", t);
    // }
    // getchar();
    // cout << (int)(log(4) / log(2)) << endl;
    while (t--)
    {
        //     cout << t << endl;
        //     // cout << (2563 % 11) << endl;
        //     // cout << t << endl;
        solve();
        //     // cout << (((float)1) << 63) << endl;
        //     // cout << '\0' << endl;
        //     // cout << f(4);
        //     // cout<<(25 >> 5)
        //     // cout << gcd(31415, 14142);//
        //     // cout << (28284 / 11) << endl;
    }
    return 0;
}

/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *                               神兽保佑            永无BUG
 */

/**
 *  ┏┓   ┏┓+ +
 * ┏┛┻━━━┛┻┓ + +
 * ┃       ┃
 * ┃   ━   ┃ ++ + + +
 *  ████━████+
 *  ◥██◤ ◥██◤ +
 * ┃   ┻   ┃
 * ┃       ┃ + +
 * ┗━┓   ┏━┛
 *   ┃   ┃ + + + +Code is far away from  
 *   ┃   ┃ + bug with the animal protecting
 *   ┃    ┗━━━┓ 神兽保佑,代码无bug 
 *   ┃        ┣┓
 *    ┃        ┏┛
 *     ┗┓┓┏━┳┓┏┛ + + + +
 *    ┃┫┫ ┃┫┫
 *    ┗┻┛ ┗┻┛+ + + +
 */
View Code

G.和而不同

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define maxn 201005
#define mod 998244353
#define pi 3.141592653
#define P 131
#define inf 1e9
#define int long long
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return x*f;
}    
int dis[1200][1200],n;
map<int,int>vis;
signed main()
{
    n=read();
    int temp=1;
    for(rg int i=1;i<n;++i)
    {
        int now=i;
        int nxt=i+1;
        for(rg int j=now;j>=1;--j)
        {
            while(vis[temp+dis[j][now]]==1) 
            {
                ++temp; 
                j=now+1;
            }
        }
        dis[now][nxt]=dis[nxt][now]=temp;
        vis[temp]=1;
        for(rg int j=now;j>=1;--j)
        {
            dis[j][nxt]=dis[nxt][j]=dis[j][now]+dis[now][nxt];
            vis[dis[j][nxt]]=1;
        }
    }
    cout<<n-1<<endl;
    for(rg int i=1;i<n;++i)
    {
        cout<<i<<" "<<i+1<<" "<<dis[i][i+1]<<endl;
    }
}
View Code

H.字符游戏

#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fi first
#define se second
#define lc u << 1
#define rc u << 1 | 1
// #define int long long

// #define double long long
// #define int __int128_t
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e7 + 10;

// const int R = 999997;
const int Base = N / 2;
const int M = 1e6 + 10;

// const int P = 1 << 10;
const int INF = 2147483647;

typedef unsigned long long ULL;

const double eps = 1e-4;
const double PI = acos(-1);
const int mod = 1e9 + 7;
int n, k;
int d;
int m;
int Q;
int target;
// int p = INF;
// __int128_t a = 1;

// rope<int> r;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
char s[1010];

void solve()
{
    scanf("%d", &n);
    vector<vector<int>> cnt(n + 1, vector<int>(27));
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        for (int j = 1; j <= len; j++)
        {
            cnt[i][s[j] - 'a']++;
        }
    }
    int ans = -1;
    for (int i = 0; i < 26; i++)
    {
        bool flag = true;
        unordered_map<int, bool> mp;
        for (int j = 1; j <= n; j++)
        {
            if (!mp.count(cnt[j][i]))
            {
                mp[cnt[j][i]] = true;
            }
            else
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            ans = i;
            break;
        }
    }
    // cout << ans << endl;
    if (ans == -1)
    {
        puts("NO");
    }
    else
    {
        puts("YES");
        string str = "";
        for (int i = 0; i < 26; i++)
        {
            if (i != ans)
            {
                str += i + 'a';
            }
        }
        str += ans + 'a';
        cout << str << endl;
    }
}

signed main()
{
    int t = 1;
    // str = "codeforces";
    // init();
    // cout << cnt << endl;
    // init();
    // scanf("%d", &t);
    // getchar();
    // int a = 1;
    // for (int i = 1; i <= 26; i++)
    // {
    //     a = (a << 1) + 1;
    // }
    // cout << a << endl;
    // float t = 134217727;
    // int cnt = 200;
    // printf("%.16lf", t);
    // while (cnt--)
    // {
    //     t = t * 2 + a;
    //     printf("%.16f\n", t);
    // }
    // getchar();
    // cout << (int)(log(4) / log(2)) << endl;
    while (t--)
    {
        //     cout << t << endl;
        //     // cout << (2563 % 11) << endl;
        //     // cout << t << endl;
        solve();
        //     // cout << (((float)1) << 63) << endl;
        //     // cout << '\0' << endl;
        //     // cout << f(4);
        //     // cout<<(25 >> 5)
        //     // cout << gcd(31415, 14142);//
        //     // cout << (28284 / 11) << endl;
    }
    return 0;
}

/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *                               神兽保佑            永无BUG
 */

/**
 *  ┏┓   ┏┓+ +
 * ┏┛┻━━━┛┻┓ + +
 * ┃       ┃
 * ┃   ━   ┃ ++ + + +
 *  ████━████+
 *  ◥██◤ ◥██◤ +
 * ┃   ┻   ┃
 * ┃       ┃ + +
 * ┗━┓   ┏━┛
 *   ┃   ┃ + + + +Code is far away from  
 *   ┃   ┃ + bug with the animal protecting
 *   ┃    ┗━━━┓ 神兽保佑,代码无bug 
 *   ┃        ┣┓
 *    ┃        ┏┛
 *     ┗┓┓┏━┳┓┏┛ + + + +
 *    ┃┫┫ ┃┫┫
 *    ┗┻┛ ┗┻┛+ + + +
 */
View Code

M.斑马子树

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define maxn 201005
#define mod 998244353
#define pi 3.141592653
#define P 131
#define inf 1e9
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return x*f;
}    
int n;
struct node
{
    int v,nxt;
}s[maxn];
int head[maxn],tot;
inline void add(int x,int y)
{
    s[++tot].v=y;
    s[tot].nxt=head[x];
    head[x]=tot;
} 
int ce[maxn],t[maxn],ans[maxn];
inline pair<int,int> dfs(int now)
{
    int l=t[now],r=t[now];
    for(rg int i=head[now];i;i=s[i].nxt)
    {
        auto nxt=dfs(s[i].v);
        l=min(l,nxt.first);
        r=max(r,nxt.second);
    }
    ans[l]++;
    ans[r]--;
    return make_pair(l,r);
}
int S[maxn];
int main()
{
    n=read();
    for(rg int i=1;i<n;++i) add(read(),i+1);
    for(rg int i=1;i<=n;++i) 
    {
        ce[i]=read();
        t[ce[i]]=i;
    }
    dfs(1);
    for(rg int i=1;i<=n;++i)
    {
        S[i]=S[i-1]+ans[i];
        printf("%d ",S[i]);
    }
}
View Code

N.栈列

#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fi first
#define se second
#define lc u << 1
#define rc u << 1 | 1
// #define int long long

// #define double long long
// #define int __int128_t
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e7 + 10;

// const int R = 999997;
const int Base = N / 2;
const int M = 1e6 + 10;

// const int P = 1 << 10;
const int INF = 2147483647;

typedef unsigned long long ULL;

const double eps = 1e-4;
const double PI = acos(-1);
const int mod = 1e9 + 7;
int n, k;
int d;
int m;
int Q;
int target;
// int p = INF;
// __int128_t a = 1;

// rope<int> r;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
char s[1010];

void solve()
{
    scanf("%d %d", &n, &m);
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    vector<int> v(n + 1);
    int mc = 0;
    int pos = 0;
    unordered_map<int, int> cnt;
    int num = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &v[i]);
        if (i > 1 && v[i] <= v[i - 1])
        {
            num++;
            pos = v[i];
        }
        cnt[v[i]]++;
        if (cnt[v[i]] > mc)
        {
            mc = cnt[v[i]];
            pos = v[i];
        }
        else if (cnt[v[i]] == mc && v[i] > pos)
        {
            pos = v[i];
        }
        else if (v[i] > pos)
        {
            pos = v[i];
        }
    }
    // cout << pos << endl;
    // cout << pos << endl;
    LL res = (LL)m * num - (m - pos - 1);
    // cout << res << endl;
    LL ans = (LL)a * res;
    // cout << ans << endl;
    ans += (LL)b * (res - n);
    for (int i = 2; i <= n; i++)
    {
        if (v[i] == 0)
        {
            if (v[i - 1] != m - 1)
            {
                ans += c;
                break;
            }
        }
        else
        {
            if (v[i - 1] != v[i] - 1)
            {
                ans += c;
                break;
            }
        }
    }

    printf("%lld\n", ans);
}

signed main()
{
    int t = 1;
    // str = "codeforces";
    // init();
    // cout << cnt << endl;
    // init();
    // scanf("%d", &t);
    // getchar();
    // int a = 1;
    // for (int i = 1; i <= 26; i++)
    // {
    //     a = (a << 1) + 1;
    // }
    // cout << a << endl;
    // float t = 134217727;
    // int cnt = 200;
    // printf("%.16lf", t);
    // while (cnt--)
    // {
    //     t = t * 2 + a;
    //     printf("%.16f\n", t);
    // }
    // getchar();
    // cout << (int)(log(4) / log(2)) << endl;
    while (t--)
    {
        //     cout << t << endl;
        //     // cout << (2563 % 11) << endl;
        //     // cout << t << endl;
        solve();
        //     // cout << (((float)1) << 63) << endl;
        //     // cout << '\0' << endl;
        //     // cout << f(4);
        //     // cout<<(25 >> 5)
        //     // cout << gcd(31415, 14142);//
        //     // cout << (28284 / 11) << endl;
    }
    return 0;
}

/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *                               神兽保佑            永无BUG
 */

/**
 *  ┏┓   ┏┓+ +
 * ┏┛┻━━━┛┻┓ + +
 * ┃       ┃
 * ┃   ━   ┃ ++ + + +
 *  ████━████+
 *  ◥██◤ ◥██◤ +
 * ┃   ┻   ┃
 * ┃       ┃ + +
 * ┗━┓   ┏━┛
 *   ┃   ┃ + + + +Code is far away from  
 *   ┃   ┃ + bug with the animal protecting
 *   ┃    ┗━━━┓ 神兽保佑,代码无bug 
 *   ┃        ┣┓
 *    ┃        ┏┛
 *     ┗┓┓┏━┳┓┏┛ + + + +
 *    ┃┫┫ ┃┫┫
 *    ┗┻┛ ┗┻┛+ + + +
 */
View Code

O.打则

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define maxn 4200000
#define inf 1e15
#define mod 19961
#define int long long
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<1)+(x<<3)+c-48;
        c=getchar(); 
    }
    return x*f;
}
int n,m,k,s;
bool vis[maxn];
int ans=1;
signed main()
{
    n=read();
    m=read();
    for(rg int i=1;i<=m;++i)
    {
        k=read();
        for(rg int j=1;j<=k;++j) s=read();
    }
    for(rg int i=1;i<=n;++i) ans=1*ans*i%mod;
    cout<<ans;
}
View Code

 

热门相关:仙城纪      性爱少女7   夫人,你马甲又掉了!   最强反套路系统