【切题】CodePlus 2017 11月月赛

乱搞记

我好菜啊！！！

为了打CP12月月赛，先切了11月的题玩玩。

T1：晨跑

传送门：LOJ6248

没错就是道水题，lcm求一发就好了。

T2：汀博尔

传送门：LOJ6249

第一眼感觉是二分答案+判定，写完交一发WA了，发现卡题意了，改完还是二分答案+判定，然后就A了。

T3：找爸爸

传送门：LOJ6250

显然可以dp，似乎有很多种dp方法，用$\large f_{i,j,0/1/2}$表示第一行到$i$，第二行到$j$，最后有无空时两行长度相同，这一状态下的最大相似度，由于不可能一二两行同一位都有空（否则就是空匹配空）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define N 3200
const char c[4]={'A','T','G','C'};
int n,m,p,q,f[N][N][3],d[300][300];
char s1[N],s2[N];
int main(){
    scanf("%s%s",s1+1,s2+1);
    n=strlen(s1+1); m=strlen(s2+1);
    for (int i=0;i<4;i++)
        for (int j=0;j<4;j++) scanf("%d",&d[c[i]][c[j]]);
    scanf("%d%d",&p,&q);
    memset(f,0x88,sizeof f); f[0][0][0]=0;
    for (int i=1;i<=n;i++) f[i][0][2]=-p-q*(i-1);
    for (int i=1;i<=m;i++) f[0][i][1]=-p-q*(i-1);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            f[i][j][0]=max(f[i-1][j-1][0],max(f[i-1][j-1][1],f[i-1][j-1][2]))+d[s1[i]][s2[j]];
            f[i][j][1]=max(f[i][j-1][0]-p,max(f[i][j-1][1]-q,f[i][j-1][2]-p));
            f[i][j][2]=max(f[i-1][j][0]-p,max(f[i-1][j][1]-p,f[i-1][j][2]-q));
        }
    printf("%d\n",max(f[n][m][0],max(f[n][m][1],f[n][m][2])));
    return 0;
}

T4：可做题

传送门：LOJ6251

嗯div2似乎还挺水的，至少一眼秒了吧！FLAG

按位处理，每一段连续的0和1的个数差是一定的，所以只要考虑前一个就好了。于是贪心一下即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define N 300000
#define LL long long
LL n,m,ans;
struct node{LL i,x;}a[N];
bool cmp(node p,node q){return p.i<q.i;}
int main(){
    scanf("%lld%lld",&n,&m);
    for (LL i=1;i<=m;i++) scanf("%lld%lld",&a[i].i,&a[i].x);
    sort(a+1,a+m+1,cmp);
    for (LL i=0;i<=30;i++){
        for (LL j=1;j<=m;j++){
            LL t,k,cnt1=0,cnt2=0;
            if ((t=(a[j].x>>i))&1) cnt1++; else cnt2++;
            for (k=j+1;k<=m && a[k].i==a[k-1].i+1;k++)
                if ((t^=(a[k].x>>i))&1) cnt1++; else cnt2++;
            if (a[j].i==1) ans+=cnt1<<i;
            else{
                if (cnt1<=cnt2+1) ans+=cnt1<<i;
                else ans+=(cnt2+1)<<i;
            }
            j=k-1;
        }
    }
    printf("%lld\n",ans);
}

T5：大吉大利，晚上吃鸡！

传送门：LOJ6252

这道题似乎就有点毒了。

如果$(A,B)$满足条件，则：

  • $F(A)+F(B)=F(总)$
  • A,B不在一条最短路上

前者可以dp，后者bitset维护传递闭包（DAG）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 60000
#define P(x,y) make_pair((x),(y))
const LL mod=10000007;
LL n,m,s,t,x,y,z,cnt,tot,ans,dp[N][2],head[N],q[N],dist[N],hsh[12000000];
bitset<N> f[N],g[N];
bool vis[N];
priority_queue< pair<LL,LL>,vector< pair<LL,LL> >,greater< pair<LL,LL> > > pq;
struct edge{LL v,nxt,l;}e[N*2];
LL getnxt(LL &x){return (++x)%n;}
void add(LL x,LL y,LL z){e[++tot].v=y; e[tot].nxt=head[x]; e[tot].l=z; head[x]=tot;}
void dij(){
    memset(dist,0x3f,sizeof dist); pq.push(P(0,s)); dist[s]=0;
    while (!pq.empty()){
        pair<LL,LL> pr=pq.top(); pq.pop();
        LL d=pr.first,u=pr.second;
        if (vis[u]) continue;
        vis[u]=1; q[++q[0]]=u;
        for (LL i=head[u],v;i;i=e[i].nxt){
            if (dist[v=e[i].v]>d+e[i].l){dist[v]=d+e[i].l; pq.push(P(dist[v],v));}
        }
    }
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for (LL i=1;i<=m;i++){
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z); add(y,x,z);
    }
    dij();
    dp[s][0]=1;
    for (LL i=1,u;i<=q[0];i++)
        for (LL j=head[u=q[i]],v;j;j=e[j].nxt)
            if (dist[v=e[j].v]==dist[u]+e[j].l) (dp[v][0]+=dp[u][0])%=mod;
    dp[t][1]=1;
    for (LL i=q[0],u;i>=1;i--)
        for (LL j=head[u=q[i]],v;j;j=e[j].nxt){
            v=e[j].v;
            if (dist[u]==dist[v=e[j].v]+e[j].l) (dp[v][1]+=dp[u][1])%=mod;
        }
    if (dp[t][0]==0){printf("%lld\n",(LL)n*(n-1)/2); return 0;}
    for (LL i=q[0],u;i>=1;i--){
        u=q[i]; f[u][u]=1;
        if (dp[u][0]*dp[u][1]){
            for (LL j=head[u],v;j;j=e[j].nxt){
                v=e[j].v;
                if (dp[v][0]*dp[v][1] && dist[u]==dist[v]+e[j].l) f[v]|=f[u];
            }
        }
    }
    for (LL i=1;i<=n;i++){
        LL tmp=(LL)dp[i][0]*dp[i][1]%mod;
        if (!hsh[tmp]) hsh[tmp]=++cnt;
        g[hsh[tmp]][i]=1;
    }
    for (LL i=1;i<=q[0];i++){
        int u=q[i];
        LL j=hsh[(mod+dp[t][0]-(LL)dp[u][0]*dp[u][1]%mod)%mod];
        g[hsh[(LL)dp[u][0]*dp[u][1]%mod]][u]=0;
        ans+=((~f[u])&g[j]).count();
    }
    printf("%lld\n",ans);
    return 0;
}

T6：Yazid 的新生舞会

传送门：LOJ6253

似乎有一万种做法，这里讲一种分治的做法（srO lych_cys）

转换一波题目可以发现要求的是有多少个区间有绝对众数。

考虑任意的区间$[l,r]$，如果$[l,r]$满足条件，则对于任意$k$，都满足$[l,k],[k+1,r]$中至少有一个区间有绝对众数。

考虑分治，则区间[l,r]中$[l,mid],[mid+1,r]$中至少有一个区间有绝对众数，可以从$mid$开始，预处理出所有可能的绝对众数（每一区间显然不超过$log(len)$个），所以总时间是$O(nlog^2n)$的。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#include<sys/mman.h>
using namespace std;
#define N 600000
#define LL long long
int n,m,a[N],hsh[N],cnt[N*2],c[N];
LL ans;
#ifdef ONLINE_JUDGE
char *s=(char*)mmap(0,1<<27,PROT_READ,MAP_PRIVATE,fileno(stdin),0);
inline int gcc(){return *(s++);}
#else
inline int gcc(){return getchar();}
#endif // ONLINE_JUDGE
#define D isdigit(c=gcc())
inline int getint(){
	int x=0,c;for(;!D;);for(x=c-'0';D;x=x*10+c-'0');
	return x;
}
inline int min(int x,int y){return x<y?x:y;}
void solve(int l,int r){
    if (l==r){ans++; return;}
    if (l>r) return;
    int mid=(l+r)>>1;
    solve(l,mid); solve(mid+1,r);
    int xb=0;
    for (int i=mid;i>=l;i--)
        if (++cnt[a[i]]<<1>mid-i+1){
            if (!hsh[a[i]]) hsh[a[i]]=++xb; c[hsh[a[i]]]=a[i];
        }
    for (int i=mid+1;i<=r;i++)
        if (++cnt[a[i]]<<1>i-mid){
            if (!hsh[a[i]]) hsh[a[i]]=++xb; c[hsh[a[i]]]=a[i];
        }
    for (int i=l;i<=r;i++) hsh[a[i]]=cnt[a[i]]=0;
    for (int i=1;i<=xb;i++){
        int sum=r-l+1,mn=sum,mx=sum; cnt[sum]=1;
        for (int j=l;j<mid;j++){++cnt[sum+=(a[j]==c[i]?1:-1)]; mn=min(mn,sum); mx=max(mx,sum);}
        sum+=a[mid]==c[i]?1:-1;
        for (int j=mn+1;j<=mx;j++) cnt[j]+=cnt[j-1];
        for (int j=mid+1;j<=r;j++){
            ans+=cnt[min(mx,(sum+=(a[j]==c[i]?1:-1))-1)];
        }
		memset(cnt+mn,0,sizeof(int)*(mx-mn+1));
    }
}
int main(){
    n=getint(); m=getint();
    for (int i=1;i<=n;i++) a[i]=getint();
    solve(1,n);
    printf("%lld\n",ans);
    return 0;
}

我好菜啊！！！！！！