2019 ICPC Asia-East Continent Final
in GYM训练 with 0 comment

2019 ICPC Asia-East Continent Final

in GYM训练 with 0 comment

摘要

/ABCDEFGHIJKLM
场上
zyj
wrf
lmj

题目

A.City

题意

题解

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=100020;

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

int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    ll n=read(),m=read();
    n++;
    m++;
    ll ans=0;

    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            ll l=min(i,n-i+1),r=min(j,m-j+1);
            // printf("%d %d %d %d\n",l,r,2*l-1,2*r-1);

            ans+=((2*l-1)*(2*r-1)-1)/2;
        }
    }

    printf("%lld",ans);
    
    return 0;
}

B.Black and White

题意

题解

代码


C.Dirichlet $k$-th root

题意

题解

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=100020;

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

typedef vector<ll> vec;

vec ind;

vec operator*(vec &a,vec &b)
{
    int n=a.size()-1;
    vec c(n+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j+=i)
        {
            c[j]=(a[i]*b[j/i]%mod+c[j])%mod;
        }
    }
    return c;
}
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b>0)
    {
        if(b%2) ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}
vec qpow(vec a,ll b)
{
    vec ans(ind);
    while(b>0)
    {
        if(b%2) ans=ans*a;
        a=a*a;
        b/=2;
    }
    return ans;
}

int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    ll n=read(),k=read();
    vec a(n+1);

    ind.resize(n+1);
    ind[1]=1;
    for(int i=0;i<n;i++)
    {
        a[i+1]=read();
    }
    vec b(qpow(a,qpow(k,mod-2)));
    // for(int j=1;j<=2*mod;j++)
    // {printf("#%d: ",j);
        for(int i=1;i<=n;i++)
        {
            printf("%lld ",b[i]);
        }
    //     printf("\n");
    //     b=b*a;
    // }
    
    return 0;
}

D.Fire

题意

题解

代码


E.Flow

题意

给定一些从1到n的路径,保证路径长度相同,每条路径上的边都有一个容量,可以进行一种操作,将一条边的容量给另一条边一个单位,求使得总流量最大时所需要的最少操作数。

题解

如果要使得总流量最大,那么最后的结果应该是每个路径上的每条边的容量基本相同,而各个路径的容量可以不相同。但可以得到,每条路径的最小容量边的总和应该等于最大流量,所以考虑将每条路径按照容量进行排序,求和,再计算其和最大流量差多少,即为最少操作数。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
vector<pair<int,ll> >v[N];
vector<ll>v1[N];
int cnt=0;
int n,m;
void dfs(int x,int fa)
{
    if(x==n)return;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].first==fa)continue;
        v1[cnt].push_back(v[x][i].second);
        dfs(v[x][i].first,x);
    }
}
int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    scanf("%d%d",&n,&m);
    ll sum=0;
    for(int i=1;i<=m;i++){
        int x,y;
        ll z;
        scanf("%d%d%lld",&x,&y,&z);
        v[x].push_back({y,z});
        v[y].push_back({x,z});
        sum+=z;
    }
    for(int i=0;i<v[1].size();i++){
        v1[++cnt].push_back(v[1][i].second);
        dfs(v[1][i].first,1);
        sort(v1[cnt].begin(),v1[cnt].end());
    }
    sum/=v1[1].size();
    ll ans=0;
    for(int i=0;i<v1[1].size();i++){
        ll sum1=0;
        for(int j=1;j<=cnt;j++){
            sum1+=v1[j][i];
        }
        if(sum1<=sum)ans+=sum-sum1;
    }
    printf("%lld\n",ans);
    return 0;
}

F.Game

题意

题解

代码


G.Happiness

题意

题解

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int ac_time[330][20],wa_num[330][20],rk[330],solve_list[330][20],n;
int req_time[20],soc[330],ac_num[330],fir_ac[20],pro_id[20],ac_num_n;
int min_ac_time=mod,max_ac_time=-1;
bool isnum(char c){return c>='0'&&c<='9';}
int read(int &x){
    char c=getchar();
    while(c!='-'&&!isnum(c)) c=getchar();
    if(c=='-') return (x=-1);
    while(isnum(c)){x=x*10+c-'0';c=getchar();}
    return x;
}
bool cmp(int x,int y){
    if(ac_num[x]!=ac_num[y]) return ac_num[x]>ac_num[y];//过题数
    if(soc[x]!=soc[y]) return soc[x]<soc[y];//罚时
    rep(i,1,ac_num[x]) if(solve_list[x][i]!=solve_list[y][i]) return solve_list[x][i]<solve_list[y][i];
    return x>y;
}
int get_rk(){
    int l=1,r=n-1,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(cmp(n,rk[mid])) r=mid-1;
        else l=mid+1,ans=mid;
    }return ans+1;
}
int main(){
    scanf("%d",&n);
    rep(i,1,10) fir_ac[i]=330;
    rep(i,1,n-1){
        rep(j,1,10) if(read(ac_time[i][j])!=-1){
            read(wa_num[i][j]);
            solve_list[i][++ac_num[i]]=ac_time[i][j];
            min_ac_time=min(min_ac_time,ac_time[i][j]);
            max_ac_time=max(max_ac_time,ac_time[i][j]);
            fir_ac[j]=min(fir_ac[j],ac_time[i][j]);
            soc[i]+=ac_time[i][j]+20*wa_num[i][j];
        }rk[i]=i;
        sort(solve_list[i]+1,solve_list[i]+1+ac_num[i],greater<int>());
    }sort(rk+1,rk+1+n-1,cmp);
    rep(i,1,10) if(read(req_time[i])!=-1){
        read(wa_num[n][i]);pro_id[++ac_num_n]=i;
    }
    // rep(i,1,10) printf("%d %d\n",ac_time[1][i],wa_num[1][i]);
    int ans=0;
    do{
        int tmp=0,now=0;
        soc[n]=ac_num[n]=0;
        rep(i,1,ac_num_n){
            if(now+req_time[pro_id[i]]>300) break;
            now+=req_time[pro_id[i]];
            soc[n]+=now+wa_num[n][pro_id[i]]*20;
            solve_list[n][++ac_num[n]]=now;
            if(now<=fir_ac[pro_id[i]]) tmp+=800;
            if(i==1&&now<=min_ac_time) tmp+=700;
        }
        if(ac_num[n]&&now>=max_ac_time) tmp+=500;
        for(int i=1, j=ac_num[n]; i < j; i++, j--) swap(solve_list[n][i], solve_list[n][j]);
        rk[n]=get_rk();tmp+=5000/rk[n];
        if(rk[n]<=n/10) tmp+=1200;
        else if(rk[n]<=3 * n/10) tmp+=800;
        else if(rk[n]<=6 * n/10) tmp+=400;
        ans=max(ans, tmp);
    }while(next_permutation(pro_id+1,pro_id+1+ac_num_n));
    printf("%d\n",ans);
}

H.King

题意

给定一个数组,求该数组是否存在一个长度超过$n/2$的子序列,使得该子序列的后一个为前一个乘相同的值获得。

题解

只用判断是否超过n/2个,那么考虑超过n/2个的时候,大概率答案存在$a[i-2],a[i]$或者$a[i-1],a[i]$,那么考虑将每个点与其前两个位置的点的商求出来。如果一个个进行判断,那么会T掉,由于如果答案为YES的话,商的重复率较高,所以取超过$n/5$次的商来进行判断

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
ll mod;
const double eps=1e-3;

const int N=200020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll qpow(ll a,ll n)
{
    ll res=1;
    while(n){
        if(n&1)res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
int n;
ll b[N];
ll inv[N];
struct node
{
    ll v;
    int sum;
}q[N*2];
bool cmp(node x,node y)
{
    return x.sum>y.sum;
}
void solve()
{
    scanf("%d%lld",&n,&mod);
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
        inv[i]=qpow(b[i],mod-2);
    }
    map<ll,int>m;
    for(int i=2;i<=n;i++){
        for(int j=max(1,i-2);j<i;j++){
            m[inv[i]*b[j]%mod]++;
        }
    }
    int tot=0;
    for(auto x:m){
        q[++tot].v=x.first;
        q[tot].sum=x.second;
    }
    int ans=0;
    sort(q+1,q+tot+1,cmp);
    for(int i=1;i<=tot;i++){
        if(q[i].sum<n/5)break;
        ll tmp=q[i].v;
        unordered_map<ll,int>m1;
        for(int j=1;j<=n;j++){
            ll tmp1=b[j]*tmp%mod;
            m1[b[j]]=max(m1[b[j]],m1[tmp1]+1);
            ans=max(ans,m1[b[j]]);
        }
    }
    if(ans*2<n){
        printf("-1\n");
    }else{
        printf("%d\n",ans);
    }
}
int main(void) 
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
    
    return 0;
}

I.Moon

题意

题解

代码


J.Permutation

题意

题解

代码


K.All Pair Maximum Flow

题意

题解

代码


L.Travel

题意

题解

代码


M.Value

题意

给定两个序列$a,b$,可以从$1-n$中选一个子集$A$,对于每个$i$属于$A$,将$a[i]$加入答案,对于$i>=2,j>=2$属于$A$,如果存在$k$,使得$i^k==j$,那么减去$b[j]$,求能获得的最高分。

题解

由于互有影响的数字较少,分组暴力dfs枚举即可。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int a[N],b[N];
int pos[25];
int vis1[25];
int vis[N];
int tot;
ll tmp=0;
void dfs(int x,ll cnt)
{
    if(x==tot+1){
        // for(int i=1;i<=tot;i++){
        //     printf("%d ",vis1[i]);
        // }
        // printf("%d\n",cnt);
        tmp=max(tmp,cnt);return;
    }
    vis1[x]=0;
    dfs(x+1,cnt);
    vis1[x]=1;
    cnt+=a[pos[x]];
    for(int i=1;i<x;i++){
        if(vis1[i]&&x%i==0){
            cnt-=b[pos[x]];
        }
    }
    dfs(x+1,cnt);
}
int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    int n=read();
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    vis[1]=1;
    ll ans=0;
    ans+=a[1];
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            tot=0;
            ll x=i;
            while(x<=n){
                pos[++tot]=x;
                vis[x]=1;
                x*=i;
            }
            tmp=0;
            dfs(1,0);
            ans+=tmp;
        }
    }
    printf("%lld\n",ans);
    return 0;
}
Responses