2019-2020 ICPC NWERC 2019
in GYM训练 with 0 comment

2019-2020 ICPC NWERC 2019

in GYM训练 with 0 comment

摘要

/ABCDEFGHIJK
场上
zyj
wrf
lmj

题目

A.Average Rank

(03:16:00) +0

题意

有$w$天,每天有$k_i$个人分数加一,求每个人每天排名的平均值

题解

考虑对于某一个人,其分数加一,只会对其当前分数和下一个分数产生影响,记录该影响即可

代码

#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=300020;

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 val[N];
ll lz[N];
ll last[N];
ll tmp[N];
ll ans[N];
ll pre[N];
int main(void)
{
    int n,w;
    n=read(),w=read();
    for(int i=1;i<=w;i++){
        int k;
        scanf("%d",&k);
        while(k--){
            int x;
            scanf("%d",&x);
            tmp[val[x]]+=lz[val[x]]*(i-last[val[x]]);
            lz[val[x]]++;
            last[val[x]]=i;
            ans[x]+=tmp[val[x]]-pre[x];
            val[x]++;
            tmp[val[x]]+=lz[val[x]]*(i-last[val[x]]);
            last[val[x]]=i;
            pre[x]=tmp[val[x]];
        }
    }
    for(int i=1;i<=n;i++){
        //printf("%lld %lld %lld\n",val[i],lz[val[i]],tmp[val[i]]);
        tmp[val[i]]+=lz[val[i]]*(w+1-last[val[i]]);
        last[val[i]]=w+1;
        ans[i]+=tmp[val[i]]-pre[i];
    }
    for(int i=1;i<=n;i++){
        printf("%.9f\n",1.0*ans[i]/w+1);
    }
    return 0;
}

B.Balanced Cut

题意

题解

代码


C.Canvas Line

(01:52:00) +0

题意

题解

代码

#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 n,q,l[N],r[N],x[N],num[N];
map<int,int> mp;
int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&l[i],&r[i]);
    scanf("%d",&q);
    for(int i=1;i<=q;i++) scanf("%d",&x[i]),mp[x[i]]=1;
    for(int i=1;i<=q;i++) for(int j=1;j<=n;++j){
        if(x[i]>=l[j]&&x[i]<=r[j]) num[j]++;
    }
    //for(int i=1;i<=n;++i) printf("%d\n",num[i]);
    for(int i=1;i<=n;++i) if(num[i]>2) return puts("impossible"),0;
    vector<int> ans;
    for(int i=2;i<=n;++i) if(l[i]==r[i-1]&&num[i-1]<2&&num[i]<2&&!mp.count(l[i])){
        ans.push_back(l[i]);num[i]++;num[i-1]++;mp[l[i]]=1;
    }
    for(int i=1;i<=n;++i) if(num[i]==2){
        mp[l[i]]=mp[r[i]]=1;
    }
    for(int i=1;i<=n;++i) while(num[i]<2){
        for(int j=l[i];j<=r[i];++j) if(!mp.count(j)){
            num[i]++;ans.push_back(j);mp[j]=1;break;
        }
    }
    printf("%d\n",ans.size());
    for(auto u:ans) printf("%d ",u);
    
    
    return 0;
}

D.Disposable Switches

(04:34:00) +12

题意

给定$n$个点,$m$条边,$l$为路径长度,$v$为速度,$c$为每走一条边所需要的代价,$v>0$,$c>=0$,取任意值,走从$1$到$n$的最短路,求图中哪些边必不可能被经过。

题解

考虑走$j$条边到$i$的最小长度,这样可以得到走到$n$时经过$1$到$n-1$条路的最短路径,可以发现可以将其变成一条线段$y=v*c*k+l$,$k$为边数,$l$为路径长度,这$n-1$条直线画在二维平面中,我们需要的只有这些直线构成的最下面的一条折线,那么就变成了一个求下凸包,考虑使用单调栈解决,求出哪些线段可以位于最下面的折线,将该条路径上的点标记,最后答案就是没标记的点数

代码

#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=10000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;
 
const int N=4020;
 
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;
}
 
struct node{int v,w,nxt;}g[N<<4];
int head[N],tot=1;
void add(int u,int v,int w){
    g[tot]={v,w,head[u]};head[u]=tot++;
}
int n,m;
ll dp[N][N];
int vis[N];
int vis1[N][N];
void dfs(int x,int k)
{
    if(vis1[x][k])return;
    vis1[x][k]=1;
    vis[x]=1;
    if(k==0)return;
    for(int i=head[x];i;i=g[i].nxt){
        if(dp[x][k]==dp[g[i].v][k-1]+g[i].w){
            dfs(g[i].v,k-1);
        }
    }
}
int cross(pair<ll,ll> a,pair<ll,ll> b, pair<ll,ll> c)
{
    return (__int128)(c.first-a.first)*(b.second-a.second)<(__int128)(c.second-a.second)*(b.first-a.first);
}
pair<ll,ll>sta[N];
int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j]=linf;
        }
    }
    dp[1][0]=0;
    for(int j=1;j<=n-1;j++){
        for(int i=1;i<=n;i++){
            for(int k=head[i];k;k=g[k].nxt){
                dp[i][j]=min(dp[i][j],dp[g[k].v][j-1]+g[k].w);
            }
        }
    }
    int cnt=0;
    for(int i=n-1;i>=1;i--){
        pair<ll,ll> tmp={i,dp[n][i]};
        while(cnt>=2&&cross(sta[cnt-1],sta[cnt],tmp))cnt--;
        if(cnt==1&&sta[cnt].second>tmp.second)cnt--;
        sta[++cnt]=tmp;
    }
    for(int i=1;i<=cnt;i++){
        //printf("%d %lld\n",sta[i].first,sta[i].second);
        dfs(n,sta[i].first);
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            sum++;
        }
    }
    printf("%d\n",sum);
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            printf("%d ",i);
        }
    }
    printf("\n");
    
    return 0;
}

E.Expeditious Cubing

(01:57:00) +3

题意

有$5$次成绩,成绩为去掉最大值去掉最小值后中间三个值的平均值,现在给定前四个成绩,再给定一个限制,求最大的值使得最后的成绩小于等于该限制,如果任意取都可以,输出$infinite$,如果任意取都不行,输出$impossible$,$1<=v<=20$

题解

给定值均为两位小数,考虑将其变成整数,这样不会有精度误差,然后分别考虑当前值作为最大值,作为最小值,作为中间值求解即可。

代码

#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[5];
double x;
int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    for(int i=1;i<=4;i++) {
        scanf("%lf",&x);
        a[i]=(int)(x*100+0.5);
    }
    scanf("%lf",&x);
    int k=(int)(x*300+0.5);
    sort(a+1,a+1+4);
    int L=(a[1]+a[2]+a[3]),R=(a[4]+a[2]+a[3]);
    if(R<=k) puts("infinite");
    else if (L>k) puts("impossible");
    else{
        printf("%.2f\n",(k-a[2]-a[3])/100.0);
    }
    
    return 0;
}

F.Firetrucks Are Red

(01:14:00) +0

题意

给定$n$个点和其上面的$m_i$个权值,两个点之间有边当且仅当这两个点中有权值相同,求一种方案将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=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;
}
vector<int>v[N];
vector<int>v1[N];
struct node
{
    int l,r,v;
}ans[N];

int fa[N];
int find(int x)
{
    if(x!=fa[x])return fa[x]=find(fa[x]);
    return x;
}
void uni(int x,int y)
{
    x=find(x),y=find(y);
    if(x!=y){
        fa[x]=y;
    }
}
int q[N];
int tot=0;
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++){
        fa[i]=i;
        int m=read();
        for(int j=1;j<=m;j++){
            int x=read();
            v[i].push_back(x);
            q[++tot]=x;
        }
    }
    sort(q+1,q+tot+1);
    tot=unique(q+1,q+tot+1)-q-1;
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<v[i].size();j++){
            int x=lower_bound(q+1,q+tot+1,v[i][j])-q;
            v1[x].push_back(i);
        }
    }
    for(int i=1;i<=tot;i++){
        for(int j=1;j<v1[i].size();j++){
            if(find(v1[i][0])!=find(v1[i][j])){
                ans[++cnt]=(node){v1[i][0],v1[i][j],q[i]};
                uni(v1[i][0],v1[i][j]);
            }
        }
    }
    if(cnt<n-1){
        printf("impossible\n");
    }else{
        for(int i=1;i<=cnt;i++){
            printf("%d %d %d\n",ans[i].l,ans[i].r,ans[i].v);
        }
    }
    return 0;
}

G.Gnoll Hypothesis

(02:30:00) +0

题意

从$n$个点中选$k$个点,所有未被选中的点,其的概率将会叠加到下一个点,求每个点被选中的概率。

题解

考虑计算每个点对于其他点的贡献,$ans[i]=\sum_{j=0}^{n-k}p[i-j]*C_{n-j-1}^{k-1}/C_{n}^{k}$

代码

c=[]
for i in range(0,512):
    c.append([])
    for j in range(0,512):
        if j==0 or j==i:
            c[i].append(1)
        elif j>i:
            c[i].append(0)
        else:
            c[i].append(c[i-1][j-1]+c[i-1][j])


[n,k]=input().split(' ')
n=int(n)
k=int(k)
s=input().split(' ')
for i in range(n):
    s[i]=int(round(float(s[i])*1000000))
    # print(i)
s+=s

ss=[]
for i in range(n):
    ss.append(0)
for i in range(0,n):
    for j in range(i,i+n):
        ss[j%n]+=c[n-(j-i+1)][k-1]*s[i]
        # print([i,j,ss])

for i in ss:
    print(i/c[n][k]/1000000,end=' ')

# print(500%7)

H.Height Profile

题意

题解

代码


I.Inverted Deck

(00:59:00) +3

题意

给定一个序列,如果其可以是某一个非递减序列翻转某一段得到,那么输出翻转的区间,否则输出$impossible$

题解

如果出现了翻转,那么显然是一段非递增的序列,考虑记录每一段非递增序列(必须出现递减时才记录),只有一段是才可以,注意要额外考虑翻转回去后端点是否满足条件

代码

#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=1000020;

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];

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]);
    }
    int l=1,r=0;
    int ansl=1,ansr=1;
    bool f=0;
    bool f1=0;
    for(int i=2;i<=n;i++){
        if(a[i]<=a[i-1]){
            r=i;
            if(a[i]<a[i-1]){
                f1=1;
            }
        }else{
            if(f1){
                 if(l<r){
                    if(f){
                        printf("impossible\n");return 0;
                    }else{
                        f=1;
                        ansl=l,ansr=r;
                        if(a[r]<a[l-1]){
                            printf("impossible\n");return 0;
                        }
                    }
                }
            }
            f1=0;
            l=i;
        }
    }
    if(f1){
        if(l<r){
            if(f){
                printf("impossible\n");return 0;
            }else{
                f=1;
                ansl=l,ansr=r;
                if(a[r]<a[l-1]){
                    printf("impossible\n");return 0;
                }
            }
        }
    }
    printf("%d %d\n",ansl,ansr);
    return 0;
}

J.Jackdaws And Crows

赛后

题意

给定$n$个数,可以用$r$的代价,删去某个点,或者用$c$的代价使得任意个数加一或者减一,可以一部分加一,一部分减一,求最少的代价,使得序列变成相邻异号

题解

首先考虑只有删除,那么将相邻同号和$0$全部删除,再考虑加减,可以使用$abs(a[i])+1$步操作使得$i$这个位置符号取反,那么按照权值从小到大枚举,同时记录当前最少需要删多少点。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=5e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[N];
int q[N];
int pre[N];
int nxt[N];
vector<int>v[N];
void work()
{
    int n,c,r;
    scanf("%d%d%d",&n,&c,&r);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        q[i]=abs(a[i]);
    }
    sort(q+1,q+n+1);
    int tot=unique(q+1,q+n+1)-q-1;
    for(int i=1;i<=n;i++){
        v[lower_bound(q+1,q+tot+1,abs(a[i]))-q].push_back(i);
    }
    for(int i=1;i<=n;i++){
        if(a[i-1]!=0)pre[i]=i-1;
        else pre[i]=pre[i-1];
    }
    for(int i=n;i>=1;i--){
        if(a[i+1]!=0)nxt[i]=i+1;
        else nxt[i]=nxt[i+1];
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]!=0&&pre[i]!=0){
            if(1ll*a[i]*a[pre[i]]>0)cnt++;
        }else if(a[i]==0)cnt++;
    }
    ll ans=1ll*cnt*r;
    cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]!=0&&pre[i]!=0){
            if(1ll*a[i]*a[pre[i]]>0&&(i-pre[i]-1)%2==0)cnt++;
            if(1ll*a[i]*a[pre[i]]<0&&(i-pre[i]-1)%2==1)cnt++;
        }
    }
    ans=min(ans,1ll*cnt*r+c);
    for(int i=1+(q[1]==0);i<=tot;i++){
        for(int j=0;j<v[i].size();j++){
            int x=v[i][j];
            if(pre[x]){
                if(1ll*a[x]*a[pre[x]]>0&&(x-pre[x]-1)%2==0)cnt--;
                if(1ll*a[x]*a[pre[x]]<0&&(x-pre[x]-1)%2==1)cnt--;
            }
            if(nxt[x]!=n+1){
                if(1ll*a[x]*a[nxt[x]]>0&&(nxt[x]-x-1)%2==0)cnt--;
                if(1ll*a[x]*a[nxt[x]]<0&&(nxt[x]-x-1)%2==1)cnt--;
            }
            if(pre[x]&&nxt[x]!=n+1){
                if(1ll*a[pre[x]]*a[nxt[x]]>0&&(nxt[x]-pre[x]-1)%2==0)cnt++;
                if(1ll*a[pre[x]]*a[nxt[x]]<0&&(nxt[x]-pre[x]-1)%2==1)cnt++;
            }
            nxt[pre[x]]=nxt[x];
            pre[nxt[x]]=pre[x];
        }
        ans=min(ans,1ll*cnt*r+1ll*c*(q[i]+1));
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

K.Kitesurfing

题意

题解

代码

Responses