春季月考 #2

做题顺序：\(\texttt{B} \to \texttt{A} \to \texttt{C} \to \texttt{D} \to \texttt{E}\)

A. 牛奶

首先可以发现，除了全部都是 \(\texttt{L/R}\) 的情况，其他的情况一定可以把数组分割成几段全部都是 \(\texttt{L,R}\) 的段。像是这样：\(\texttt{RRRLLRLLL}\)

• 如果当前段是 \(\texttt{R}\) 段，那么所有的牛奶都会向着最后一个 \(\texttt{R}\) 的右边推进，像这样：\(\texttt{3210} \to \texttt{2211} \to \texttt{1212} \to \texttt{0213} \to \texttt{0114} \to \cdots\)。
• 左边必然是一个 \(\texttt{L}\) 段，于是会出现这样子的情况，\(\texttt{L/R}\) 交界处两只满了的牛互相给对方奶，后面推上来的奶全部作废：\(\texttt{32112} \to \texttt{22111} \to \texttt{12110} \to \texttt{02110} \to \texttt{01110} \to \texttt{00110} \to \texttt{00110} \to \cdots\)
• 所以，对于每一个 \(\texttt{RRR} \cdots \texttt{RRLL} \cdots \texttt{LL}\) 的这种段
  • 从 \(\texttt{R}\) 串的开头开始浪费牛奶，到达倒数第二只牛之后，就没法浪费了。
  • 从 \(\texttt{L}\) 串的末尾开始浪费牛奶，到达倒数第二只牛之后，就没法浪费了。
• 但是这样子不太好找，所以我们搞一个环形的链表，直接找 \(\texttt{LR}\)，相当于找到了两组 \(\texttt{RL}\) 的其中一个开头，然后从中间开始向两边浪费。

评价：奇奇妙妙。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int Prev[200005],Next[200005];
int N,M,a[200005],ans;
char s[200005];
bool ISL,ISR;

void Make_Dlist(int N){
    for(int i=1;i<=N;i++){
        Prev[i]=i-1,Next[i]=i+1;
    }Prev[1]=N,Next[N]=1;
}

signed main()
{
    ISL=ISR=false;
    scanf("%lld%lld",&N,&M);
    scanf("%s",s+1);
    for(int i=1;i<=N;i++){
        scanf("%lld",&a[i]);ans+=a[i];
        if(s[i]=='L') ISL=true;
        if(s[i]=='R') ISR=true;
    }
    if(!ISL or !ISR){
        printf("%lld",ans);
    }else{
        Make_Dlist(N);
        for(int i=1;i<=N;i++){
            int l=i,r=Next[i];
            if(s[l]=='L' and s[r]=='R'){
                int waste=0;
                while(s[Prev[l]]!='R'){
                    if(waste+a[l]<M) waste+=a[l];
                    else             {waste=M;break;}
                    l=Prev[l];
                }ans-=waste;

                waste=0;
                while(s[Next[r]]!='L'){
                    if(waste+a[r]<M) waste+=a[r];
                    else             {waste=M;break;}
                    r=Next[r];
                }ans-=waste;
            }
        }
        printf("%lld",ans);
    }
    return 0;
}

B. 起床

通过每一个农场的最短到达时间和关闭时间，可以计算出至少要在哪个时刻之前起床，才能访问到这个农场。树状数组搞一搞就好了。

#include <bits/stdc++.h>
using namespace std;

int N,c[200005],t[200005];
int s[200005],tot;
int Q,V,S;

struct Tree_array{
    int Tree[1000005];
    int lowbit(int x){return x&-x;}
    void Modify(int pos,int k){
        while(pos<=1e6){
            Tree[pos]+=k;
            pos+=lowbit(pos);
        }
    }
    int Query(int r){
        int res=0;
        while(r){
            res+=Tree[r];
            r-=lowbit(r);
        }return res;
    }
}Farm;

int main()
{
    scanf("%d%d",&N,&Q);
    for(int i=1;i<=N;i++) scanf("%d",&c[i]);
    for(int i=1;i<=N;i++) scanf("%d",&t[i]);
    for(int i=1;i<=N;i++) s[i]=c[i]-t[i]-1;
    for(int i=1;i<=N;i++) if(s[i]>0) Farm.Modify(s[i],1),tot++;
    for(int i=1;i<=Q;i++){
        scanf("%d%d",&V,&S);
        if(tot-Farm.Query(S-1)<V) puts("NO");
        else                      puts("YES");
    }
    return 0;
}

C. 游戏

我们不妨来先搞一个事情，求出每一回合游戏中，Elsie 最好情况下会损失多少。

然后题目中有一句话：Even 的字典序小于 Odd。

所以说我们要尽可能的选择出偶数。

那就每一次假设当前位置出偶数，看一下够不够输，不够就出单数。

挺好的题。

#include <bits/stdc++.h>
using namespace std;
const int inf=0x7fffffff;

int F[300005][2],Min[300005];
int N,M,K,a[300005][5];

void Init(){
	for(int i=1;i<=M+1;i++){
		F[i][0]=F[i][1]=inf;
		Min[i]=0;
	}
	for(int i=1;i<=M;i++){
		for(int j=1;j<=K;j++){
			int flag=a[i][j]%2;
			F[i][flag]=min(F[i][flag],a[i][j]);
			F[i][flag^1]=min(F[i][flag^1],-a[i][j]);
		}
	}
	for(int i=M;i>=1;i--){
        Min[i]=min(0,max(F[i][0],F[i][1])+Min[i+1]);
    }
}

void Main()
{
	scanf("%d%d%d",&N,&M,&K);
	for(int i=1;i<=M;i++){
		for(int j=1;j<=K;j++){
			scanf("%d",&a[i][j]);
		}
	}
    Init();
	if(N+Min[1]<=0){
		puts("-1");
	}else{
        int Have=N;
        for(int i=1;i<=M;i++){
            if(Have+F[i][0]+Min[i+1]<=0) printf("Odd "),Have+=F[i][1];
            else                         printf("Even "),Have+=F[i][0];
        }puts("");
    }
	return; 
}

int T;
int main()
{
	scanf("%d",&T);
	while(T--){
        Main();
    }
	return 0;
}

D. 充电

暴力。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int Head[505],Next[2005],tot;
int Val[2005],Go[2005];
void Add_edge(int u,int v,int w){
	tot++,Next[tot]=Head[u],Head[u]=tot,Go[tot]=v,Val[tot]=w;
}

priority_queue<pii,vector<pii>,greater<pii> >q;
bool vis[505][505];
int dis[505][505];
void Dijkstra(int s){
	memset(dis[s],0x3f,sizeof(dis[s]));dis[s][s]=0;
	memset(vis[s],false,sizeof(vis[s]));
	q.push({0,s});
	while(!q.empty()){
		int u=q.top().second;q.pop();
		if(vis[s][u])continue;vis[s][u]=true;
		for(int i=Head[u];i;i=Next[i]){
			int v=Go[i];
			if(dis[s][v]>dis[s][u]+Val[i]){
				dis[s][v]=dis[s][u]+Val[i];
				q.push({dis[s][v],v});
			}
		}
	}
}

int N,M,C,R,K,ans[505],totans;
int u,v,w;

int main()
{
    scanf("%d%d%d%d%d",&N,&M,&C,&R,&K);
    for(int i=1;i<=M;i++){
        scanf("%d%d%d",&u,&v,&w);
        Add_edge(u,v,w);
        Add_edge(v,u,w);
    }
    for(int i=1;i<=C;i++){
        Dijkstra(i);
    }
    for(int v=C+1;v<=N;v++){
        int cnt=0;
        for(int u=1;u<=C;u++){
            if(dis[u][v]<=R) cnt++;
        }if(cnt>=K) ans[++totans]=v;
    }
    printf("%d\n",totans);
    for(int i=1;i<=totans;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

E. Data Structure Problem

样例。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    puts("20190813");
    puts("2668638611");
    puts("549902096");
    return 0;
}