练习12

practise

A 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int x,bs,ans;
int main(){
    cin>>x;
    bs=1;
    while(x){
        ans+=(x%10*bs);
        x/=10;bs*=8;
    }
    cout<<ans<<endl;
    return 0;
}

B 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int a[110],p,B;
bool f(int x){
    p=0;
    while(x){
        a[++p]=x%B;
        x/=B;
    }
    rep(i,1,p){
        if(a[i]!=a[p+1-i])
            return false;
    }
    return true;
}
void pt(int x){
    stack<int> s;
    while(x){
        s.push(x%B);
        x/=B;
    }
    while(!s.empty()){
        int t=s.top();s.pop();
        printf("%c",(t<=9)?'0'+t:'A'+(t-10));
    }
}
int main(){
    cin>>B;
    rep(i,1,300){
        if(f(i*i)){
            pt(i);putchar(' ');
            pt(i*i);putchar('\n');  
        }
    }
    return 0;
}

C 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int t,a[200010],mx[200010],n;
int get(int x){
    if(x<=1)    return a[x]=x;
    if(a[x])    return a[x];
    if(x%2) return a[x]=get(x/2)+get(x/2+1);
    else    return a[x]=get(x/2);
}
int main(){
    rep(i,1,100000){
        get(i);
    }
    rep(i,1,100000){
        mx[i]=max(a[i],mx[i-1]);
    }
    cin>>t;
    while(t--){
        cin>>n;
        printf("%d\n",mx[n]);
    }
    return 0;
}

D 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
vector<int> g[2010];
int n,tmp,rt[2010];
int dfs(int now,int fa){
    int dep=0;
    for(auto to:g[now]){
        if(to==fa)  continue;
        dep=max(dep,dfs(to,now));
    }
    return dep+1;
}
int main(){
    cin>>n;
    rep(i,1,n){
        cin>>tmp;
        if(tmp==-1){
            rt[i]=1;
            continue;
        }
        g[tmp].pb(i);
        g[i].pb(tmp);
    }
    int ans=0;
    rep(i,1,n){
        if(rt[i])   ans=max(ans,dfs(i,i));
    }
    cout<<ans<<endl;
    return 0;
}

E 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int cnt[30],n,vis[30];
char s[1000010];
bool m[30][30];
vector<int> g[30];
pii dfs(int now){
    pii ret=make_pair(cnt[now],cnt[now]);
    vis[now]=1;
    for(auto to:g[now]){
        if(vis[to]) continue;
        pii sv=dfs(to);
        ret.first+=sv.first;
        ret.second=max(ret.second,sv.second);
    }
    return ret;
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    rep(i,1,n/2){
        cnt[s[i]-'a'+1]++;
        cnt[s[n+1-i]-'a'+1]++;
        m[s[i]-'a'+1][s[n+1-i]-'a'+1]=1;
        m[s[n+1-i]-'a'+1][s[i]-'a'+1]=1;
    }
    if(n%2) cnt[s[n/2+1]-'a'+1]++;
    rep(i,1,26){
        rep(j,i+1,26){
            if(m[i][j]){
                g[i].pb(j);
                g[j].pb(i);
            }
        }
    }
    int ans=0;
    rep(i,1,26){
        if(!vis[i]){
            pii res=dfs(i);
            assert(res.first>=res.second);
            ans+=(res.first-res.second);
        }
    }
    printf("%d\n",ans); 
    return 0;
}
/*
tongrentang
gnatnergnot
abbaa
*/

F 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
ll n;
bool p(ll x){
    for(int i=2;(ll)i*i<=x;i++){
        if(x%(ll)i==0)  return false;
    }
    return true;
}
int main(){
    cin>>n;
    while(1){
        if(p(n)){
            printf("%lld\n",n);
            return 0;
        }
        n--;
    }
    return 0;
}

G IC1101

using namespace std;
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb(X) push_back(X)
#define x first
#define y second
#define all(x) (x).begin(), (x).end()
#define bbb 0;
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
typedef long long ll;
typedef vector<int> VI;
typedef vector<long long> VL;
typedef pair<int, int> pii;
//ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int MAXN = 1e3 + 7;
int _, __, DP[MAXN][MAXN];
int main() {
    INIT
    DP[1][0] = 1;
    cin >> _ >> __;
    rep (i, 1, _ + 1)
    rep (j, 0, __ + 1)
    rep (k, 0, i)
    if(j >= k) (DP[i][j] += DP[i - 1][j - k]) %= 10000;
    cout << DP[_][__];
    if ("bbb") return bbb;
}

H 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
struct edg{
    int f,t;
    ll w;
};
struct nod{
    int x,y,no;
};
int n,p,fat[100010];
edg e[200010];
nod a[200010];
int find(int x){
    if(fat[x]==x)   return x;
    return fat[x]=find(fat[x]);
}
void merge(int x,int y){
    fat[find(x)]=find(y);
}
bool cmp(edg a,edg b){
    return a.w<b.w;
}
bool cmp1(nod a,nod b){
    return a.x<b.x;
}
bool cmp2(nod a,nod b){
    return a.y<b.y;
}
edg tmp;
ll ans;
int main(){
    cin>>n;
    rep(i,1,n){
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].no=i;
    }
    sort(a+1,a+1+n,cmp1);
    rep(i,2,n){
        tmp.f=a[i-1].no;
        tmp.t=a[i].no;
        tmp.w=a[i].x-a[i-1].x;
        e[++p]=tmp;
    }
    sort(a+1,a+1+n,cmp2);
    rep(i,2,n){
        tmp.f=a[i-1].no;
        tmp.t=a[i].no;
        tmp.w=a[i].y-a[i-1].y;
        e[++p]=tmp;
    }
    sort(e+1,e+1+p,cmp);
    for(int i=1;i<=n;i++){
        fat[i]=i;
    }
    for(int i=1;i<=p;i++){
        int x=find(e[i].f),y=find(e[i].t);
        if(x==y){
            continue;
        }
        merge(x,y);
        ans+=e[i].w;
    }
    printf("%lld\n",ans);
    return 0;
}

I anananan

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int qp(int a,int b,int mod)
{
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
int euler(int n){
    int ret=n;
    for(int i=2; i*i<=n; i++)
        if(n%i==0){
            ret=ret-ret/i;
            do n/=i;
            while(n%i==0);
        }
    if(n>1)ret=ret-ret/n;
    return ret;
}
map<int,int>ma;
int solve(int x)
{
    if(ma.find(x)!=ma.end()) return ma[x];
    int tem=euler(x);
    return ma[x]=qp(2,solve(tem)+tem,x);
}
int main()
{
    int t; cin>>t;
    while(t--){
        ma[1]=0;
        int p; scanf("%d",&p);
        printf("%d\n",solve(p));
    }
}