T1

Description

小 H 最近迷上了名为“石头,剪刀,布”的游戏。
游戏规则很简单:比赛双方同时数到三,然后同时出一个手势,代表“石
头”、“剪刀”或“布”。“石头”胜“剪刀”,“剪刀”胜“布”,“布”胜“石
头”。举个例子, 小 H 出“石头”, 对方出“布”,则对方胜利。当然,也可
以“平局”(如果双方手势相同的话)。
小 H 对阵小 B。 小 H 作为一个匹托专家,能够预测小 B 未来 N 回合的手
势。 但作为具有数学头脑的人, 他又是比较懒的,以至于他只愿意变换固
定次数的手势来完成游戏。例如, 他只想变 1 次,则他可能出“石头”几
次,剩下的都出“布”;或者其他。
现在小 H 与小 B 准备进行 N 回合的比赛,且已经测出小 B 未来 N 回合
的手势,小 H 只愿意改变 K 次手势(最开始手势任意)。请你帮小 H 求出他
最多能赢多少场

Input

输入文件名为 game.in。
输入的第一行两个空格隔开的数字 N 和 K,分别表示比赛的回合数和
小 H 变换手势的次数。 接下来的 N 行,每行一个字母,表示小 B 的手势: ’H’
表示石头、 ’S’表示剪刀、 ’P’表示布

Output

输出文件名为 game.out。
输出一行一个整数, 小 H 最多能赢的场数

Sample Input

5 1
P P H P S

Sample Output

4

Hint

对于 30%的数据: N≤20
对于 100%的数据: N≤100 000, K≤20

Solution

一道水水的dp啊qwq,刷表和i-1到i转移都可以。注意细节...O($n \ast k$)实现就欧克。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
using namespace std;
#define maxn 100005
int n,k,a[maxn],dp[maxn][22][3];//0:石头,1:剪刀,2:布 
char s[2];
void init(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){scanf("%s",s);if(s[0]=='H')a[i]=0;if(s[0]=='S') a[i]=1;if(s[0]=='P') a[i]=2;};
    //dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=0;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=min(i,k);j++)
    for(int kk=0;kk<=2;kk++){//枚举上一个的手势 
        int f=0;
        if(a[i]==2&&kk==1) f=1; 
        if(a[i]==1&&kk==0) f=1;
        if(a[i]==0&&kk==2) f=1;
        dp[i][j][kk]=max(dp[i][j][kk],dp[i-1][j][kk]+f);//不换
        int tt=(a[i]-1+3)%3;
        if(j>=1){
            if(tt==kk) continue;//不换..对身体好 
            dp[i][j][tt]=max(dp[i][j][tt],dp[i-1][j-1][kk]+1); 
        }
    }
    int maxx=0;
    for(int i=0;i<=2;i++) maxx=max(maxx,dp[n][k][i]);
    printf("%d",maxx);
} 
int main(){
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    init();
    
    return 0;
}

T2

Description

为补贴家用,小 M 终于谋得一份兼职——牛奶销售员。
小 M 打算把牛奶销售到 N 个城市,这 N 个城市编号为 1..N。这些城市
之间有 R 条高速公路和 P 条泥泞小道连接。每条高速路或泥泞小道连接 N
个城市中的 A 和 B, 需要的花费为 C,对于高速路的花费 C, 一定是大于等
于 0 的;然而对于泥泞小道,由于边远城市的人民感谢送奶工的辛劳,会
额外付更多的奶钱, 所以有些小道的花费可能为负数(表示有收益)。高速
公路是双向的,可以从 A 走到 B,也可以从 B 走到 A;然后泥泞小道则不是
双向的,只能从 A 走到 B。事实上, 由于泥泞道路经过的都是蛮荒之地,所
以政府为了社会和谐,出台了一些政策保证: 如果一条泥泞小道可以从 A
到 B,那么保证不可能通过高速路或泥泞小道从 B 再回到 A。
小 M 的销售中心在城市 S,现在他想知道,把牛奶从 S 送到每个城市的
最小花费的,或者根本就不能送到。

Input

输入文件名为 sales.in。
输入的第 1 行包含四个空格隔开的整数: N, R, P 和 S,他们的意义如题
目描述。 第 2 到 R+1 行每行含三个空格隔开的整数: A, B 和 C,表示一条高
速公路双向连接城市 A 和 B,需要的花费为 C。 第 R+2 到 R+P+1 行每行包含
三个空格隔开的整数: A, B 和 C,表示一条泥泞小道可以从城市 A 到 B,需
要的花费为 C。

Output

输出文件名为 sales.out。
输出有 N 行,每行一个整数,第 i 行表示从 S 到达城市 i 的最小花费,
如果不存在输出"NO PATH"。

Sample Input

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

Sample Output

NO PATH
NO PATH
5
0
-95
-100

Hint

对于 30%的数据: N≤10 000
对于 100%的数据: 1≤N≤25,000 , 1≤P,R≤50,000
高速公路的 C: 0≤C≤10,000
泥泞小道的 C: -10,000≤C≤10,000

Solution

这道题真的傻缺了啊qwq,别人想的是有负权边不能跑dij,我tm想的是没有负环直接跑dij,感觉复杂度差不多就直接交上去了哇qwq。实际上你的复杂度超乎你想象。
开始正经:
这道题有两种解法:
1.spfa+slf优化,好像勉强过得到?直接用双端队列deque维护一下。slf优化还是能加就加吧,毕竟挺简单的。不过关于spfa,<font color=red>它已经死了.</font>所以稳妥一点还是用dij吧,对身体好a.
2.dij+缩点+拓扑:woc这个思路真的很nice啊,首先发现可以缩点连成一个DAG图,然后对于每个联通块单独跑dij,这样算下来总复杂度也就nlogn左右(事实证明真的跑得飞快!法1时间几乎是它的十倍).然后就是注意细节的实现,也为这种混合图提供了一种思路。当把所有的入边处理完之后用vector记录入点,就可以队首存入多个起点,一次dij跑完,复杂度被大大减少.(可以回顾noip2017逛公园).

上代码:

#include<bits/stdc++.h>
#define maxn 25005
#define maxm 150005
using namespace std;
struct eage{
    int to,next,len;
}e[maxm];
int np=0,first[maxn];
void add(int u,int v,int len){
    e[++np]=(eage){v,first[u],len};
    first[u]=np;
}
int n,r,p,s,x,y,z,dfn[maxn],low[maxn],belong[maxn],cc=0,clock_=0;
int st[maxn],top=0,rd[maxn];
bool vis[maxn];
vector<int>g[maxn];
struct noded{
    int from,to,len;
};
vector<noded>b[maxn];
void dfs(int i,int f){
    vis[i]=1;
    st[++top]=i;
    low[i]=dfn[i]=++clock_;
    for(int p=first[i];p;p=e[p].next){
        int j=e[p].to;
        if(vis[j]){
            if(!belong[j]) low[i]=min(low[i],dfn[j]);
            continue;
        }
        dfs(j,i);
        low[i]=min(low[i],low[j]);
    }
    if(low[i]==dfn[i]){
        cc++;
        while(1){
            int t=st[top--];
            belong[t]=cc;
            if(t==i) break;
        } 
    }
}
int dist[maxn];
bool viss[maxn];
struct node{
    int v,id;
    friend bool operator <(node a,node b){
        return a.v>b.v;
    }
};
void dij(int s){
    priority_queue<node>q;
    for(int i=0;i<g[s].size();i++){
        int t=g[s][i];
        q.push((node){dist[t],t});
    }
    while(!q.empty()){
        node t=q.top();q.pop();
        int i=t.id;
        if(viss[i]) continue;
        viss[i]=1;
        for(int p=first[i];p;p=e[p].next){
            int j=e[p].to,c=e[p].len;
            if(belong[j]!=belong[i]) continue;
            if(dist[j]>dist[i]+c){
                dist[j]=dist[i]+c;
                q.push((node){dist[j],j});
            }
        }
    }    
} 
queue<int>qq;
void work(){
    memset(viss,0,sizeof(viss));
    for(int i=1;i<=n;i++) dist[i]=1000000007;
    g[belong[s]].push_back(s);
    dist[s]=0;
    qq.push(belong[s]);
    while(!qq.empty()){
       int i=qq.front();qq.pop();
       dij(i);
       for(int j=0;j<b[i].size();j++){
           noded tt=b[i][j];
           int t1=tt.from,t2=tt.to,c=tt.len;
           dist[t2]=min(dist[t2],dist[t1]+c);
           g[belong[t2]].push_back(t2);
           rd[belong[t2]]--;
           if(rd[belong[t2]]==0) qq.push(belong[t2]);
       }
    } 
    for(int i=1;i<=n;i++){
        if(dist[i]==1000000007) printf("NO PATH\n");
        else printf("%d\n",dist[i]);
    }
} 
void run(){
    for(int i=1;i<=n;i++){
        if(!vis[i]) continue;
        for(int p=first[i];p;p=e[p].next){
            int j=e[p].to;
            if(belong[j]!=belong[i]){
                //g[belong[i]].push_back(belong[j]);
                b[belong[i]].push_back((noded){i,j,e[p].len});
                rd[belong[j]]++;
            }
        }
    }
    
    work();
}
void init(){
    scanf("%d%d%d%d",&n,&r,&p,&s);
    for(int i=1;i<=r;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=p;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    dfs(s,0);
    run();
}
int main(){
    init();
    
    return 0;
}

T3

Description

小 Y 同学手上有两类线段,分别为 A 线段和 B 线段。
A 线段的有n种,第i种有$s_i$条,其左端点和右端点为$a_i$和$b_i$,他们都是109
范围内的正整数,且一定有$a_i$ ≤ $b_i$。 B 线段的有m种,第i种有$k_i$条,其左端
点和右端点为$l_i$和$r_i$,他们也是109范围内的正整数,且一定有$l_i$ ≤$r_i$。 小 Y
还规定,如果一条 A 线段($a_i$, $b_i$)能匹配一条 B 线段($l_i$, $r_i$),当且仅当$l_i$ ≤ $a_i$≤
$b_i$ ≤ $r_i$。
现在小 Y 需要你判断能否为所有的 A 线段都指定一条与之匹配的 B 线段。
注意,无论是 A 线段还是 B 线段,每条都只能匹配一次,且仅能匹配一次。

Input

输入文件名为 machine.in
输入的第 1 行是一个整数T,表示数据组数。每组数据的第 1 行有两个
整数n, m,分别表 A 类线段和 B 类线段的种类数。接下来n行,每行 3 个整
数ai、 bi、 si,描述一种 A 类线段。接下来 m 行,每行三个整数li、 ri、 ki,
描述一种 B 类线段。

Output

输入文件名为 machine.out
仅输出共T行,每行一个字符串,若可以实现则输出 Yes,否则输出
No。

Sample Input

3
2 2
1 4 2
3 5 1
1 4 2
2 5 1
3 2
1 3 1
2 4 1
3 5 1
1 3 2
2 5 1
2 2
1 2 2
1 2 1
1 2 1
1 2 2

Sample Output

Yes
No
Yes

Hint

对于所有数据保证有:
1 ≤ $s_i$, $k_i$ ≤ 109,
1 ≤ t≤ 50,
1 ≤ n, m ≤ 50000。
一个测试点中,所有n的和不超过 4000000,所有m的和也不超过 4000000。

Solution

还是一道套路题a,用set维护直接nlognA了啊(没办法蒟蒻太蒻了)。稍微注意线段维护的细节,按照左端点排序,相同排右端点。然后用两个指针维护,对于每个i,将l小于等于它的加入到multiset里面(以右端点为关键字)然后每次lower_bound找一下就欧克了啊qwq.
(勉哥说对于每个被删掉的指针要查询它的下一个必须要预先处理好)

tips

线段类的有很多问题可以总结a....上一次居然被那个线段贪心给卡了qwq(处理不重叠的最多线段)就是右端点排个序,左端点大的就可以加进去,贪贪贪

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
struct node{
    int l,r,w;
    friend bool operator <(node a,node b){
        if(a.l!=b.l)return a.l<b.l;
        else return a.r<b.r;    
    }
}nda[maxn],ndb[maxn];
struct noded{
    int r,w;
    friend bool operator <(noded a,noded b){
        return a.r<b.r;
    }
};
multiset<noded>s;
multiset<noded>::iterator it,itt;
int t,n,m;
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&nda[i].l,&nda[i].r,&nda[i].w);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&ndb[i].l,&ndb[i].r,&ndb[i].w);
    sort(nda+1,nda+n+1);
    sort(ndb+1,ndb+m+1);
    
    s.clear();
    int j=1;//b的序号 
    for(int i=1;i<=n;i++){//a的序号 
        while(j<=m&&ndb[j].l<=nda[i].l) s.insert((noded){ndb[j].r,ndb[j].w}),j++; 
        noded tt=(noded){nda[i].r,0};
        it=s.lower_bound(tt);
        if(it==s.end()) {printf("No\n");return;} 
        while(1){
        noded t=*it; s.erase(it);
        if(t.w>=nda[i].w){t.w-=nda[i].w,nda[i].w=0,s.insert((noded){t.r,t.w});break;}
        else nda[i].w-=t.w;
        it=s.lower_bound(tt);
        if(it==s.end())  {printf("No\n");return;} 
        }
    }
    printf("Yes\n");
}
int main(){
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    init();
    
    return 0;
}
Last modification:February 15th, 2019 at 09:37 pm