22/6/27

1，acwing 920 最优乘车；2，acwing 903.昂贵的聘礼；3，cf Restricted RPS

---

1，最优乘车； 

 思路：

同条线路的所有站点之间的距离为1，所以给每条线路的站点之间互连距离为1的路径，求1好点到s的最短距离，再减去1即是最少换乘次数；

这道题有个注意的地方是它每行给出的线路车站数是不确定的，所以采用行读取，用到了stringstream；简单写下用法：

行的输入用getline，（如果在你要读入的数据之前还有输入，那就要吃个回车，用了快读不能用getchar，用cin.get();），

将行的数据放到stringstream里有两种写法：

一种是stringstream ssin(line)；

一种是 stringstream ssin；ssin<<line;

将stringstream的数据取出来的方法：ssin>>();

注意区分和cin>> ; cout<< 的方向的区别；

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rep1(i,a,n) for( int i=a;i<n;++i) 
#define rep2(i,a,n) for( int i=a;i<=n;++i) 
#define per1(i,n,a) for( int i=n;i>a;i--) 
#define per2(i,n,a) for( int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i,b) memset((a),(i),sizeof (b))
#define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
#define pro_q priority_queue
#define pb push_back
#define pf push_front
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define yi first
#define er second
using namespace std;
typedef pair<long long,long long>PLL;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef long long LL;
typedef double dob;
const int N = 510;
int m,n;
int g[N][N];
int dist[N];
int stop[N];
void bfs()
{
    queue<int>q;
    memset(dist,0x3f,dist);
    q.push(1);
    dist[1]=0;
    while(q.size())
    {
        int t=q.front();q.pop();
        rep2(i,1,n)
        {
            if(g[t][i]&&dist[i]>dist[t]+1)
            {
                dist[i]=dist[t]+1;
                q.push(i);
            }
        }
    }
}
signed main()
{
    quick_cin();
    cin>>m>>n;
    string line;
    cin.get();
    while(m--)
    {
        getline(cin,line);
        stringstream ssin(line);
        int cnt=0,p;
        while(ssin>>p)stop[cnt++]=p;
        rep1(j,0,cnt)
            rep1(k,j+1,cnt)
            g[stop[j]][stop[k]]=1;
    }
    bfs();
    if(dist[n]==0x3f3f3f3f)NO;
    else cout<<max(dist[n]-1,0);
    return 0;
}

 2，昂贵的聘礼；

 题目有些长，需要耐心分析题目；

首先看不考虑等级制度的建图方式，在得到每个物品的路径上，都有一条原价直接买到的，不妨设个虚拟源点S，都由S连该路径；

拿样例来看：

我们可以从该图中得到最短的路径，几所需的金币总数，花50买4物品，在拿200 换3物品，在加5000即可得到1；

那有了等级制度后，我们只可以在等级区间内进行交易，一共100等级，可以遍历整个等级区间，来得到最优解；

 code

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rep1(i,a,n) for( int i=a;i<n;++i) 
#define rep2(i,a,n) for( int i=a;i<=n;++i) 
#define per1(i,n,a) for( int i=n;i>a;i--) 
#define per2(i,n,a) for( int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i,b) memset((a),(i),sizeof (b))
#define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
#define pro_q priority_queue
#define pb push_back
#define pf push_front
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define yi first
#define er second
using namespace std;
typedef pair<long long,long long>PLL;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef long long LL;
typedef double dob;
const int N=110,INF=0x3f3f3f3f;
int n,m;
int w[N][N],level[N];
int dist[N];
int st[N];
int dijkstra(int down,int up)
{
    memset(dist,0x3f,dist);
    memset(st,0,st);
    dist[0]=0;
    rep2(i,1,n+1)
    {
        int t=-1;
        rep2(j,0,n)
        if(!st[j]&&(t==-1||dist[t]>dist[j]))
        t=j;
        st[t]=1;
        rep2(j,1,n)
        if(level[j]>=down&&level[j]<=up)
        dist[j]=min(dist[j],dist[t]+w[t][j]);
    }
    return dist[1];
}
signed main()
{
    quick_cin();
    cin>>m>>n;
    memset(w,0x3f,w);
    rep2(i,1,n)w[i][i]=0;
    rep2(i,1,n)
    {
        int price,cnt;
        cin>>price>>level[i]>>cnt;
        w[0][i]=min(price,w[0][i]);
        while (cnt--)
        {
            int id,cost;
            cin>>id>>cost;
            w[id][i]=min(w[id][i],cost);
        }
    }
    int res=INF;
    rep2(i,level[1]-m,level[1])
    res=min(res,dijkstra(i,i+m));
    cout<<res;
    return 0;
}

3,cf Restricted RPS

题意：a和b在玩石头剪刀布游戏，有n次回合，a赢的条件是至少n/2上取整次赢；

现给出a的石头次数，剪刀次数，布次数；和b的出手序列RPPS....（R是石头，P是布，S是剪刀）

如果a能赢，输出yes和使a能赢的出手序列（任意，但是长度和b相同）；否则no；

思路：统计b的R，P，S的次数，a赢得对局的次数是min（P，R），min（S，P），min（R，S）的和；符合条件就赢，对应位置给它安排赢的出手，最后遍历没有安排到的位置给它安排出手；

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rep1(i,a,n) for( int i=a;i<n;++i) 
#define rep2(i,a,n) for( int i=a;i<=n;++i) 
#define per1(i,n,a) for( int i=n;i>a;i--) 
#define per2(i,n,a) for( int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i,b) memset((a),(i),sizeof (b))
#define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
#define pro_q priority_queue
#define pb push_back
#define pf push_front
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define yi first
#define er second
using namespace std;
typedef pair<long long,long long>PLL;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef long long LL;
typedef double dob;
unordered_map<char,int>acs;
unordered_map<char,int>bcs;
char trans(char c)
{
    if(c=='R')return 'P';
    else if(c=='P')return 'S';
    else return 'R';
}
char ans[1010];
void solve()
{
    acs.clear();
    bcs.clear();
    memset(ans,0,ans);
    int n;
    cin>>n;
    int mid=n+1>>1;
    int a,b,c;
    cin>>a>>b>>c;
    acs['R']=a;
    acs['P']=b;
    acs['S']=c;
    string s;
    cin>>s;
    int siz=s.size();
    rep1(i,0,siz)bcs[s[i]]++;
    int wins=0;
    wins+=min(a,bcs['S']);
    wins+=min(b,bcs['R']);
    wins+=min(c,bcs['P']);
    if(wins>=mid)
    {
        YES;
        rep1(i,0,siz)
        {
            if(acs[trans(s[i])])
            {
                ans[i]=trans(s[i]);
                acs[trans(s[i])]--;
            }
        }
        rep1(i,0,siz)
        {
            if(!ans[i])
            {
                if(acs['R'])ans[i]='R',acs['R']--;
                else if(acs['P'])ans[i]='P',acs['P']--;
                else ans[i]='S',acs['S']--;
            }
        }
        rep1(i,0,siz)cout<<ans[i];
        cout<<endl;
    }
    else NO;
}
signed main()
{
    quick_cin();
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}