2018-09-17发表2018-09-17更新acm4 分钟读完 (大约607个字)

The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online

The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online（青岛网络赛）

B.Red Black Tree

题意

题解

ac代码

J.Press the Button

题意

题解

ac代码

H Traveling on the Axis

题意

BOB走在$[1,n]$的路上，每两个点中间都有一个红绿灯，每一秒钟，

BOB先观察红绿灯是否绿，绿就走，红就停。
红灯变绿，绿灯变红

$t(p,q)$就是$p$走到$q所需要的时间。

问： BOB从 $\sum^{n-1}{p=0} \sum{q=p+1}^nt(p,q)$的时间总和。

题解

对于第$i$个单独的红绿灯我们可以证明他对答案的贡献是

$(i)(len-i+1)(t(i))$

我们对于两个灯进行分析。

01 第一个零要2s，第二个一要1s

10 第一个一要1s，第二个零要1s

00 第一个零要2s，第二个一要2s

11 第一个一要1s，第二个一要2s

综上可以发现，

该灯初始为0，那么他当头的时候贡献为2，如果不当头那么他的贡献就为1，除非跟前者相同。
该灯初始为1，那么他和前一个灯相同时贡献为2，就算变成0了，不在头上的话贡献也为1.

我他妈sb了，不应该看着一段一段的区间，应该把红绿灯作为每一次状态的扩展，从红绿灯这$n$个出发开始计算，不应该考虑一个一个的单位为1的区间。

AC代码

// CSL 代码
#include <bits/stdc++.h>
using namespace std;
 const int N = 1 << 17;
char s[N];
typedef long long ll;
 int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", s);
        ll ans = 0;
        int n = strlen(s);
        for (int i = 0; i < n; i++) ans += 1LL * (i + 1) * (n - i);
        for (int i = 0; s[i]; i++)
        {
            if (s[i] == '0') ans += n - i;
            if (i && (s[i] == s[i - 1])) ans += 1LL * i * (n - i);
            //要跟包含前者的可能，要两个相同才能这么加。
        }
        printf("%lld\n", ans);
    }
}

#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 = 1e5 + 10;
char s[maxn];
int main(){
#ifdef LOCAL
    freopen("h.in","r",stdin);
#endif
    int T;scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        int len = strlen(s);
        ll ans = 0; ll w = 0;
        if(s[0]=='1') ans = w = 1;
        else ans = w = 2;
        rep(i,1,len){
            if(s[i]==s[i-1]) w += i*2;
            else w += i*1;
            if(s[i]=='1') w += 1;
            else w += 2;
            ans += w;
        }
        printf("%lld\n",ans);
    }

    return 0;
}

reference:

https://blog.csdn.net/tianyizhicheng/article/details/82728350

2018-09-10发表2018-09-12更新acm7 分钟读完 (大约1024个字)

ACM-ICPC 2018 徐州赛区网络预赛

A. Hard to prepare

题意

$n$个人围成环，每个人可以选择$[0,2^k-1]$中的一个数字，要求相邻两人不能同或为0。

题解

递归。

可以YY出，第一个人有$2^k$种选择，之后第2到第$n-1$个人有$2^k-1$种选择，最后一个人可能可以选$2^k-2$，也可能可以选$2^k-1$。这取决于倒数第二个人是否跟第一个人选一样的。这时候我们就可以加上如果第一个人和倒数第二个人选择相同，并且，最后一个人多选了那$2^k-1-(2^k-2)$种，那么他们三个点变成一个点来选择了。

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 n,k;
const ll mod = 1e9+7;
ll pow3(ll a,ll b){
    ll ans = 1;
    while(b){
        if(b&1) ans = ans*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
ll k2,kk2,kk1;
ll solve(int n,int k){
    if(k==1) return 2;
    if(n==1) return k2;
    if(n==2) return k2*kk1%mod;
    ll res = (k2*kk2%mod)*pow3(kk1,n-2)%mod;
    res = (res+solve(n-2,k))%mod;
    return res;
}
int main(){
#ifdef LOCAL
    freopen("4.in","r",stdin);
#endif
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        k2 = pow3(2,k);
        kk1 = (k2-1+mod)%mod;
        kk2 = (k2-2+mod)%mod;
        printf("%lld\n",solve(n,k));
    }

    return 0;
}

B.BE,GE or NE

题意

两个人玩游戏，给出$[0,3]$个选项和一个$m$初始值，两个人依次选择，有以下三种选择

选择将值$+a$
选择将值$-b$
选择将值倒过来 $m=-m$

两个人一个想将值变大，一个想让值变小，两个人都知晓所有情况和选项，在最优情况下，问谁赢。

题解

博弈论dp+记忆化搜索

因为数据量很小，范围也在200之间，所以记忆化状态回复的很多。

$dp[pos][val]$表示在pos位置数值是val,之后dp代表的是最优可以赢还是输还是平，分别用2,1,0代表。

之后对于边界值要处理一下。数组存不了负值，我们统一加100处理。

妈的。我看到这个以为是纯博弈论直接人傻了。之后想着能不能记忆化搜索，但是看到$n=1000$还以为他喵的会爆，但是这道题的情况限制在范围$-100到100$，所以情况很少。所以可以直接记忆化，不过对于答案的选择和状态转移我可能还是不会太轻松地做出来，带int的dfs我还是不怎么熟悉，这按道理应该是算是博弈论dp了。从最优状态转移到最优状态。

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 pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
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;}
// head
int n,m,k,l;
const int maxn = 1e3 + 10;
int a[maxn],b[maxn],c[maxn];
int dp[maxn][220];
// op
int dfs(int pos,int val){
    if(pos == n){
        if(val >= k){
            return 2;
        }else if(val > l){
            return 1;
        }else{
            return 0;
        }
    }
    if(dp[pos][val] != -1) return dp[pos][val];
    if(pos%2==0){
        int res = 0;
        int mmin = min(200,val+a[pos]);
        int mmax = max(0,val-b[pos]);
        if(a[pos]) res = max(res,dfs(pos+1,mmin));
        if(b[pos]) res = max(res,dfs(pos+1,mmax));
        if(c[pos]) res = max(res,dfs(pos+1,200-val));
        return dp[pos][val] = res;
    }else{
        int res = 2;
        int mmin = min(200,val+a[pos]);
        int mmax = max(0,val-b[pos]);
        if(a[pos]) res = min(res,dfs(pos+1,mmin));
        if(b[pos]) res = min(res,dfs(pos+1,mmax));
        if(c[pos]) res = min(res,dfs(pos+1,200-val));
        return dp[pos][val] = res;
    }
}
int main(){
#ifdef LOCAL
    freopen("b.in","r",stdin);
#endif // LOCAL
    rep(i,0,maxn) rep(j,0,220) dp[i][j] = -1;
    scanf("%d%d%d%d",&n,&m,&k,&l);
    l += 100; k += 100; m += 100;
    rep(i,0,n){
        scanf("%d%d%d",a+i,b+i,c+i);
    }
    int op = dfs(0,m);
    if(op==2) puts("Good Ending");
    else if(op==1) puts("Normal Ending");
    else puts("Bad Ending");
    return 0;
}

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

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

The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online

The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online（青岛网络赛）

B.Red Black Tree

题意

题解

ac代码

J.Press the Button

题意

题解

ac代码

H Traveling on the Axis

题意

题解

AC代码

ACM-ICPC 2018 徐州赛区网络预赛

ACM-ICPC 2018 徐州赛区网络预赛

A. Hard to prepare

题意

题解

AC代码

B.BE,GE or NE

题意

题解

AC代码

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代码

链接

分类

最新文章

归档

标签

订阅更新