2018-09-03发表2018-09-04更新acm11 分钟读完 (大约1586个字)0次访问

2018 ICPC南京赛区网络赛

ACM-ICPC 2018 南京赛区网络预赛

A. An Olympian Math Problem

题意

$S=1×1!+2×2!+⋯+(n - 1) \times (n-1)!(n−1)×(n−1)!$问$Smodn$是多少。

题解

思维题，打表题？答案就是$n-1$证明如下。

看到$n-1$很不爽，那就加一个$(n-1)!$就凑好了。

$S+1!+2!+…+(n-1)!=2!+3!+…+n!$

之后再减掉。

$S=n!-1!$那么对$n$取余$S modn=-1modn=n-1$搞定。

AC代码

#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-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int T;
ll n;
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        scanf("%lld",&n);
        printf("%lld\n",n-1);
    }
    return 0;
}

B. The writing on the wall

E. AC Challenge

题意

做题目，要按照一定顺序做题目，每个题目有两个值$a,b$，表示做了题目后增加$t*a+b$。

题解

状态压缩+剪枝+拓扑排序。

因为$n$的数据量小于$20$所以可以使用状态压缩。

$S$表示已经做的题目。

$vs$数组存储已知做题的最大值。如果做同样的题值比较小就减掉。

AC代码

#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-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 30;
struct noddde{
    int next,to;
}G[maxn*maxn*3];
int head[maxn],ind[maxn];
ll a[maxn],b[maxn];
int cnt;
void add(int u,int v){
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
int n;
ll ans = 0;
ll vis[maxn];
ll vs[1<<22];
void dfs(int u,int t,ll temp,int S){
    ans = max(ans,temp);
    if(vs[S] > temp) return;
    vs[S] = temp;
    for(int i = head[u];~i;i=G[i].next){
        int v = G[i].to;
        ind[v]--;
    }
    rep(i,1,n+1){
        if(ind[i] == 0 && vis[i]==0){
            vis[i] = 1;
            dfs(i,t+1,temp+a[i]*t+b[i],S|(1<<i));
            vis[i] = 0;
        }
    }
    for(int i = head[u];~i;i=G[i].next){
        int v = G[i].to;
        ind[v]++;
    }
}
int main(){
#ifdef LOCAL
    freopen("e.in","r",stdin);
#endif
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    rep(i,1,n+1){
        int s;scanf("%lld%lld%d",&a[i],&b[i],&s);
        rep(j,0,s){
            int u;scanf("%d",&u);
            add(u,i);ind[i]++;
        }
    }
    rep(i,1,n+1){
        if(ind[i]==0){
            ind[i]++;
            add(0,i);
        }
    }
    ans = 0;
    dfs(0,1,0,0);
    printf("%lld\n",ans);
    return 0;
}

G. Lpl and Energy-saving Lamps

题意

一个人去给所有房间换灯泡，每个月都会获得$m$个灯泡，每个房间有$a_i$个灯泡，之后以能换就换的态度每个月从第一个房间开始换，没有能换的房间就停止，把灯泡留到下一个月。换过灯泡就不用再换了。问给定月份中已经换好的房间数和当月剩下的灯泡数。

题解

线段树维护一个区间最小值。

由于线段树遍历是从前往后的，就不用担心顺序问题。

AC代码

#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-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int day[maxn],remain[maxn];
int a[maxn],Min[maxn<<2],ask[maxn];
int n,m,now,ans;
void pushup(int rt){
    Min[rt] = min(Min[rt<<1],Min[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        Min[rt] = a[l];
        return;
    }
    int mid = (l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int l,int r,int rt){
    if(Min[rt] > now) return;
    if(l==r){
        now -= Min[rt];
        ans ++;
        Min[rt] = INF;
        return;
    }
    int mid = (l+r)>>1;
    update(lson);
    update(rson);
    pushup(rt);
}
int main(){
#ifdef LOCAL
    freopen("g.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,1,n+1) scanf("%d",a+i);
    int maxq = 0;int q;
    scanf("%d",&q);
    rep(i,0,q){
        scanf("%d",ask+i);
        maxq = max(maxq,ask[i]);
    }
    build(1,n,1);
    rep(i,1,maxq+1){
        now += m;
        update(1,n,1);
        day[i] = ans;remain[i] = now;
    }
    rep(i,0,q){
        printf("%d %d\n",day[ask[i]],remain[ask[i]]);
    }

    return 0;
}

I. Skr

题意

给定一个由数字构成的字符串，$n\leq 2000000$。问回文串加起来有多少？

题解

两种做法：

马拉车+hash
回文树+dfs

AC代码1

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
using namespace std;
#define ULL unsigned long long
#define ll long long
const int maxn=4000000+40;
const int mod=1e9+7;
ULL P = 1313131;
ULL sqr[maxn/2],has[maxn/2],V[maxn];
ll ha[maxn/2],tmp[maxn/2];
int Laxt[maxn],Next[maxn],cnt=0;
 
const int MOD = 2000007;

bool _insert(ULL Now)
{
       int u=Now%MOD;
       for(int i=Laxt[u];i;i=Next[i]){
        if(V[i]==Now) return true;
       }
       Next[++cnt]=Laxt[u];
       Laxt[u]=cnt;
       V[cnt]=Now;
       return false;
}
ll ans=0;
void _hash(int x,int y){
    ULL Now=has[y]-has[x-1]*sqr[y-x+1];
    if(!_insert(Now))
    {
		ans+=((ha[y]-ha[x-1]*tmp[y-x+1]%mod)%mod+mod)%mod;
		ans%=mod;
	}
} 
int r[maxn];
char c[maxn];
void _malacher()
{
    int R=0,Mid=0,Len;
    
    scanf("%s",c+1);
    Len=strlen(c+1);
    sqr[0]=tmp[0]=1;
    has[0]=ha[0]=0;
    for(int i=1;i<=Len;i++){
        sqr[i]=sqr[i-1]*P;
        has[i]=has[i-1]*P+c[i];
        tmp[i]=tmp[i-1]*10%mod;
        ha[i]=(ha[i-1]*10+c[i]-'0')%mod;
    }  
    
     for(int i=1;i<=Len;++i) {      
        _hash(i,i);
        if(R>i) r[i]=min(r[2*Mid-i],R-i);
        while(i+r[i]+1<=Len&&c[i+r[i]+1]==c[i-r[i]-1]){
            _hash(i-r[i]-1,i+r[i]+1);
            r[i]++;
        }
        if(i+r[i]>R) {
            R=i+r[i];
            Mid=i;
        }
    }
    
    cnt=0;Mid=0;R=0;
    memset(Laxt,0,sizeof(Laxt));
    memset(r,0,sizeof(r));
    for(int i=2;i<=Len;++i) {
        if(R>i) r[i]=min(r[2*Mid-i],R-i+1);
        while(i+r[i]<=Len&&c[i+r[i]]==c[i-r[i]-1]) {
            _hash(i-r[i]-1,i+r[i]);
            ++r[i];
        }
        if(i+r[i]-1>R) {
            R=i+r[i]-1;
            Mid=i;
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    _malacher();
    return 0;
}

AC代码2

#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;
const int MAXN=2005005;
const ll MOD=1000000007ll;
 
ll pow(ll a,ll b){
  ll t,y;
  t=1; y=a;
  while (b!=0){
    if (b&1==1) t=t*y%MOD;
    y=y*y%MOD; b=b>>1;
  }
  return t;
}
 
int len[MAXN];
int nxt[MAXN][15];
int fail[MAXN];
int num[MAXN];
int cnt[MAXN];
int last;
int S[MAXN];
int tot;
int N;
 
int new_node(int l){
    cnt[tot]=0;
    num[tot]=0;
    len[tot]=l;
    return tot++;
}
 
void init_tree(){
    tot=0;
    new_node(0);
    new_node(-1);
    last=0;
    N=0;
    S[N]=-1;
    fail[0]=1;
}
 
int get_fail(int x){
    while(S[N-len[x]-1]!=S[N])
        x=fail[x];
    return x;
}
 
void add_char(int c){
    c-='0';
    S[++N]=c;
    int cur=get_fail(last);
    if(!nxt[cur][c]){
        int now=new_node(len[cur]+2);
        fail[now]=nxt[get_fail(fail[cur])][c];
        nxt[cur][c]=now;
        num[now]=num[fail[now]]+1;
    }
    last=nxt[cur][c];
    cnt[last]++;
}
 
 
ll jans=0;
ll oans=0;
 
void dfs1(int x,ll fa){
	for(int i=1;i<=9;i++){
		if(nxt[x][i]){
			ll cur;
			if(len[nxt[x][i]]==1){
				jans+=i;
				cur=i;
				jans%=MOD;
			}
			else{
				cur=i*pow(10,(len[nxt[x][i]]-1))%MOD+i+fa*10%MOD;
				jans=(jans+cur%MOD)%MOD;
				jans%=MOD;
			}
			dfs1(nxt[x][i],cur%MOD);
		}
	}
}
 
void dfs2(int x,ll fa){
	
	for(int i=1;i<=9;i++){
		if(nxt[x][i]){
			ll cur;
			cur=i*pow(10,(len[nxt[x][i]]-1))%MOD+i+fa*10%MOD;
			oans=(oans+cur%MOD)%MOD;
			dfs2(nxt[x][i],cur%MOD);
		}
	}
}
 
 
char str[MAXN];
 
int main(){
 	scanf("%s",str);
 	int N1 = strlen(str);
 	init_tree();
 	for(int i=0;i<N1;i++)
 		add_char(str[i]);
 	dfs1(1,0);
 	dfs2(0,0);
 	printf("%lld\n",(jans%MOD+oans%MOD)%MOD);
    return 0;
}

L. Magical Girl Haze

题意

给定一个图，问从$1$走到$n$如果可以选择$k$条路为$0$，那么最短的路径是多少。

题解

分层图最短路+堆优化dijistra

每使用一次道路为0，就进入$step+1$的路径比较。比较好的dp思维。对于pair使用了一个小trick，负值就可以不用手写greater和重载小于了。但是现场赛应该还是手写node算了。

dp转移两种状态.

$dp[v][step+1] = min(dp[v][step+1],dp[u][step])$
$dp[v][step] = min(dp[v][step],dp[u][step]+val(u,v))$

AC代码

#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-1);i>=(a);i--)
#define fi first
#define se second
#define mp make_pair
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int T,n,m,k,cnt;
struct node{
    int to,next,val;
}G[maxn<<1];
int head[maxn];
ll dp[maxn][13],done[maxn][13];
void add(int u,int v,ll val){
    G[cnt].to = v;
    G[cnt].next = head[u];
    G[cnt].val = val;
    head[u] = cnt++;
}
void dijstra(){
    priority_queue<pair<ll,pair<int,int> > > pq;
    pq.push(mp(0,mp(1,0)));
    dp[1][0] = 0;
    while(!pq.empty()){
        int u = pq.top().se.fi;
        ll dis = pq.top().fi;
        int step = pq.top().se.se;
        pq.pop();
        if(done[u][step]) continue;
        done[u][step] = 1;
        if(u == n){
            printf("%lld\n",-dis);return;
        }
        for(int i=head[u];~i;i=G[i].next){
            int v = G[i].to;ll val = G[i].val;
            if(step<k && !done[v][step+1] && dp[v][step+1]<dis){
                dp[v][step+1] = dis;
                pq.push(mp(dis,mp(v,step+1)));
            }
            if(!done[v][step] && dp[v][step]<dis+val){
                dp[v][step] = dis+val;
                pq.push(mp(dp[v][step],mp(v,step)));
            }
        }
    }
}
void init(){
    memset(head,-1,sizeof(int)*(n+2));
    cnt = 0;
    memset(done,0,sizeof(done));
    rep(i,1,n+1) rep(j,0,k+1) dp[i][j] = -1e16;
}
int main(){
#ifdef LOCAL
    freopen("l.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        init();
        rep(i,0,m){
            int u,v;ll val;scanf("%d%d%lld",&u,&v,&val);
            add(u,v,-val);
        }
        dijstra();
    }
    return 0;
}

2018 ICPC南京赛区网络赛

https://www.cheasim.com/acm/2018/09/03/2018-ICPC%E5%8D%97%E4%BA%AC%E8%B5%9B%E5%8C%BA%E7%BD%91%E7%BB%9C%E8%B5%9B.html

作者

CheaSim

发布于

2018-09-03

更新于

2018-09-04

许可协议

#网络赛

2018 ICPC南京赛区网络赛

ACM-ICPC 2018 南京赛区网络预赛

A. An Olympian Math Problem

题意

题解

AC代码

B. The writing on the wall

E. AC Challenge

题意

题解

AC代码

G. Lpl and Energy-saving Lamps

题意

题解

AC代码

I. Skr

题意

题解

AC代码1

AC代码2

L. Magical Girl Haze

题意

题解

AC代码

作者

发布于

更新于

许可协议

喜欢这篇文章？打赏一下作者吧

评论

链接

分类

最新文章

归档

标签

订阅更新