Contest 22

contest

A lnkkerst

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    string n;
    cin >> n;
    cout << (char)*max_element(n.begin(), n.end());
    return 0;
}

B djddskkekk

#include <iostream>
using namespace std;
long long a , sum;
int main ( void )
{
    ios::sync_with_stdio ( false ); cin.tie ( 0 ); cout.tie ( 0 );
    cin >> a;
    for ( int i = 1 ; i <= a ; i++ ) {
        sum += i - 1;
    }
    cout << sum << endl;
    return 0;
}

C lnkkerst

#include <iostream>
#define int long long
using namespace std;
int n, a[11], b[11];
signed main() {
    while(cin >> n) {
        for(int i = 1; i <= n; ++i)
            cin >> a[i] >> b[i];
        int ans = b[1], t = a[1];
        for(int i = 2; i <= n; ++i) {
            while(ans % a[i] != b[i])
                ans += t;
            t *= a[i];
        }
        cout << ans << endl;
    }
    return 0;
}

D djddskkekk

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e7 + 5;
int a [ maxn ];
int n , t;
int main ( void )
{
    ios::sync_with_stdio ( false ); cin.tie ( 0 ); cout.tie ( 0 );
    for ( int i = 1 ; i <= 2e7 ; i++ ) {
        if ( a [ i + 1 ] == 0 ) {
            a [ i + 1 ] = a [ i ] + 1;
        } else {
            a [ i + 1 ] = min ( a [ i ] + 1 , a [ i + 1 ] );
        }
        if ( i * 2 <= 2e7 ) {
            if ( a [ 2 * i ] == 0 ) {
                a [ 2 * i ] = a [ i ] + 1;
            } else {
                a [ 2 * i ] = min ( a [ 2 * i ] , a [ i ] + 1 );
            }
        }
        if ( i * 3 <= 2e7 ) {
            if ( a [ 3 * i ] == 0 ) {
                a [ 3 * i ] = a [ i ] + 1;
            } else {
                a [ 3 * i ] = min ( a [ 3 * i ] , a [ i ] + 1 );
            }
        }
    }
    cin >> t;
    int cnt = 1;
    while ( t-- ) {
        cin >> n;
        cout << "Case " << cnt << ": " << a [ n ] << endl;
        cnt++;
    }
    return 0;
}

E lnkkerst

#include <iostream>
#define int long long
using namespace std;
signed main() {
    int t;
    cin >> t;
    while(t--) {
        int x;
        cin >> x;
        cout << (x >> 1) * (x - (x >> 1)) << endl;
    }
    return 0;
}

F yingyingying777

//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int phi(int n)
{
    int ans=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
        ans=ans/n*(n-1);
    return ans;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",phi(n));  
    }   
    return 0;
}

G lnkkerst

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <queue>
using namespace std;
struct Node {
    int h, v, ind;
    bool vis;
} a[200010];
struct Edge {
    int to, nex;
} e[2000010];
int n, ans, cnt = 0, no = 0;
string xs, nm, fa, tmp;
unordered_map<string, int> id;
void addedge(int u, int v) {
    e[++cnt] = (Edge){v, a[u].h};
    a[u].h = cnt;
    ++a[v].ind;
}
void topo() {
    queue<int > q;
    for(int i = 1; i <= no; ++i)
        if(!a[i].ind) q.push(i);
    while(!q.empty()) {
        int u = q.front();
        a[u].vis = 1;
        q.pop();
        for(int i = a[u].h; i; i = e[i].nex) {
            int v = e[i].to;
            --a[v].ind;
            a[v].v = max(a[v].v, a[u].v + 1);
            ans = max(ans, a[v].v);
            if(!a[v].ind) q.push(v);
        }
    }
}
void dfs(int u, int &val, int &dep) {
    a[u].vis = 1;
    val = max(val, a[u].v);
    ++dep;
    for(int i = a[u].h; i; i = e[i].nex)
        if(!a[e[i].to].vis)
            dfs(e[i].to, val, dep);
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> xs >> nm >> tmp >> tmp >> fa;
        nm = xs + ' ' + nm;
        fa = xs + ' ' + fa;
        if(!id[nm]) id[nm] = ++no;
        if(!id[fa]) id[fa] = ++no;
        addedge(id[nm], id[fa]);
    } topo();
    for(int i = 1; i <= no; ++i)
        if(!a[i].vis) {
            int val = 0, dep = 0;
            dfs(i, val, dep);
            ans = max(ans, val + dep);
        }
    cout << ans;
    return 0;
}

H djddskkekk

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int row , col , n ,top , f [ maxn ] , x_1 , y_1 , x_2 , y_2;
bool vis [ maxn ];
vector < pair < int , int > > v [ 4 ];
inline bool check ( int a , int b )
{
    if ( a == 0 || a == row || b == 0 || b == col ) {
        return true;
    } 
    return false;
}
inline int read ( )
{
    int s = 0 , t = 1; char ch = getchar ( );
    while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) t = -1; ch = getchar ( ); }
    while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ( ); }
    return s * t;
}
void get_in ( int Row , int Col , int flag )
{
    if ( !Row ) {
        v [ 0 ].emplace_back ( make_pair ( Col , flag ) );
    } else if ( col == Col ) {
        v [ 1 ].emplace_back ( make_pair ( Row , flag ) );
    } else if ( row == Row ) {
        v [ 2 ].emplace_back ( make_pair ( col - Col , flag ) );
    } else {
        v [ 3 ].emplace_back ( make_pair ( row - Row , flag ) );
    }
} 
int main ( void )
{
    row = read ( ); col = read ( ); n = read ( );
    for ( int i = 1 ; i <= n ; i++ ) {
        x_1 = read ( ); y_1 = read ( ); x_2 = read ( ); y_2 = read ( );
        if ( check ( x_1 , y_1 ) && check ( x_2 , y_2 ) ) {
            get_in ( x_1 , y_1 , i );
            get_in ( x_2 , y_2 , i );
        }
    }
    for ( int i = 0 ; i < 4 ; i++ ) {
        sort ( v [ i ].begin ( ) , v [ i ].end ( ) );
        for ( vector < pair < int , int > >::iterator x = v [ i ].begin ( ) ; x != v [ i ].end ( ) ; x++ ) {
            int flag = x->second;
            if ( !vis [ flag ] ) {
                f [ ++top ] = flag;
                vis [ flag ] = 1;
            } else if ( !top || f [ top ] != flag ) {
                puts ( "NO" );
                return 0;
            } else {
                --top;
            }
        }
    }
    puts ( "YES" );
    return 0;
}

I 6109118071

#include<iostream>
#include<set>
#include<string.h>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 100005;
int num[100005];
struct ac_atom{
    int trie[N][26], ct[N], fail[N], tot;
    void init()
    {
        memset(trie, 0, sizeof(trie));
        memset(ct, 0, sizeof(ct));
        memset(fail, 0, sizeof(fail));
        tot = 0;
    }
    void insert(char *s)
    {
        int rt = 0;
        int len = strlen(s);
        for (int i = 0; i < len; i++)
        {
            int od = s[i] - 'a';
            if (!trie[rt][od])
            {
                trie[rt][od] = ++tot;
            }
            rt = trie[rt][od];
        }
        ct[rt] = len;
    }
    void get_fail()
    {
        int rt = 0;
        fail[0] = 0;
        queue<int> q;
        for (int i = 0; i < 26; i++)
        {
            if (trie[rt][i])
            {
                fail[trie[rt][i]] = 0;
                q.push(trie[rt][i]);
            }
        }
        while (!q.empty())
        {
            int e = q.front();
            q.pop();
            for (int i = 0; i < 26; i++)
            {
                if (trie[e][i])
                {
                    fail[trie[e][i]] = trie[fail[e]][i];
                    q.push(trie[e][i]);
                }
                else
                    trie[e][i] = trie[fail[e]][i];
            }
        }
    }
    void query(char *s)
    {
        int rt = 0, ans = 0;
        int len = strlen(s);
        for (int i = 0; i < len; i++)
        {
            int od = s[i] - 'a';
            rt = trie[rt][od];
            int mx = 0;
            for (int j = rt; j; j = fail[j])
            {
                if (ct[j])
                {
                    mx = ct[j];
                }
            }
            if (mx)
                num[i] = i - mx + 2;
            else
                num[i] = 0;
        }
    }
}tmp;
int n;
char s[155];
char str[100005];
int main()
{
    while (~scanf("%s", str)){
        scanf("%d", &n);
        int l = 0, ans = 0;
        memset(num, 0, sizeof(num));
        tmp.init();
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", s);
            tmp.insert(s);
        }
        tmp.get_fail();
        tmp.query(str);
        int len = strlen(str);
        for (int i = 0; i < len; i++)
        {
            if (num[i] > l)
            {
                l = num[i];
            }
            ans = max(ans, i - l + 1);
        }
        printf("%d\n", ans);
    }
}

J

K

L _Wallace_

#include<cstdio>
using namespace std;
const int N=6e5+5;
int root[N];
namespace PerTrie
{
    const int SZ=N<<5;
    int ch[SZ][2];
    int cnt[SZ];
    int total=0;//ver. count
    int size=0;//node count
    void insert(int num)
    {
        root[++total]=++size;
        int l=root[total-1],r=root[total];
        for(register int i=24;i>=0;i--)
        {
            int c=(num>>i)&1;
            ch[r][!c]=ch[l][!c];
            ch[r][c]=++size;
            l=ch[l][c],r=ch[r][c];
            cnt[r]=cnt[l]+1;
        }
    }
    int query(int num,int l,int r)
    {
        int ret=0;
        l=root[l],r=root[r];
        for(register int i=24;i>=0;i--)
        {
            int c=(num>>i)&1;
            if(cnt[ch[r][!c]]>cnt[ch[l][!c]])
                ret|=(1<<i),c^=1;
            l=ch[l][c],r=ch[r][c];
        }
        return ret;
    }
}
signed main()
{
    int n,m,sum=0;
    scanf("%d%d",&n,&m);
    PerTrie::insert(0);
    for(register int a,i=1;i<=n;i++)
        scanf("%d",&a),PerTrie::insert(sum^=a);
    while(m--)
    {
        char op[10];
        int l,r,x;
        scanf("%s",op);
        if(op[0]=='A')
        {
            scanf("%d",&x);
            PerTrie::insert(sum^=x);
        }
        else
        {
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n",PerTrie::query(x^sum,l-1,r));
        }
    }
    return 0;
}//艹这题卡常