Codeforces Round 374 div2-蒲公英云

题目链接： CodeforcesRound374

做了这么久cf了，，c题有时候还是做不起，，真的好菜，，，，

A题：读题读了几分钟，，一开始没看懂，，其实题目里说的日本什么的字画什么的，，都是废话，，最后看了一下输入输出和样例瞬间就懂了，，，题意就是给你一串只包含字符‘B’和‘W’ 的字符串，，，问你连续的字符B出现的子串有多少个，，并且从左到右分别求出只包含B的子串的长度

例如： 3 BBW （第一个为n，，字符串长度）里面只包含一个连续B字符的子串，并且长度为2 所以输出 1 2

              5 BWBWB   包含三个连续B字符的子串  长度都为1   所以输出  3  1 1 1
              3 WWW  里面没有B  所以输出   0
             3   BBB   包含一个并且长度为3  输出  1 3
 这题懂了就很好做了，，可以用一个数组  num\[\] 记录每个子串的长度，，所以只需从左到右遍历一遍  当遇到B时就用一个while循环知道遇到W，while里面就用num计算，变量    cnt统计又多少个子串

代码：

#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<stdio.h>
#include<vector>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define lcr(a,b) memset(a,b,sizeof(a))
#define sfor(i,n) for(i=0;i<n;i++)
#define dfor(i,n) for(i=n-1;i>=0;i--)
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d\n",x)
#define ll long long
#define INF 0x7fffffff
#define esp 1e-8
int n,m;
int main()
{
    while(cin>>n)
    {
        char s[1000];
        scanf("%s",s);
        int num[1000];
        int cnt=0;
        lcr(num,0);
        for(int i=0; i<n; i++)
        {
            while(s[i]=='B'&&i<n)
            {
                num[cnt]++;
                i++;
            }
            if(num[cnt]!=0)
            {
                cnt++;
            }
        }
        printf("%d\n",cnt);
        if(cnt)
        {
            for(int i=0; i<cnt; i++)
                printf("%d ",num[i]);
            cout<<endl;
        }
    }
    return 0;
}

B题： B题一开始看错题目了，，WA了两次，，，其实只要看懂第二段话就不会看错题了，，题目意思就是 Vanya 现在有n个密码去进入一个网页，但他不知道哪一个是正确的，，所以他要一个一个去试，没试一次都将花费他1s ，，而系统只允许他错T 次，，当他错了T次还没找到正确就要等上5s 才能继续输入

而他尝试输入的顺序是密码长度从短到长，长度相同的密码必须全部试过才能试下一长度，，这里我一开始看错了，，以为可以从任意长度开始，第二段说了必须以非递减的长度尝试，，然后要求以最快的时间找出正确的密码和最慢的时间找出密码，最后输出这两个时间！

题目输入 n 和 T 然后接下来 n行，每行一个密码第n+1为正确的密码

这题其实只需一个数组记录每种长度的密码出现的个数，最后就可以得出正确的密码的长度的第一个和最后一个的位置，，因为最快的时间为当找到正确密码的长度时第一个就是正确密码，最慢为最后一个才是密码在正确的密码的长度的区间内，，，因为密码长度最长为100，，所以只需循环 1到密码的长度-1，，就可以得出正确密码长度之前又多个，这样答案就出来了，，，而计算时间的公式为第i位置上的时间 t = i + ((i-1)/T)*5，，这个不难得出

代码：

#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<stdio.h>
#include<vector>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define lcr(a,b) memset(a,b,sizeof(a))
#define sfor(i,n) for(i=0;i<n;i++)
#define dfor(i,n) for(i=n-1;i>=0;i--)
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d\n",x)
#define ll long long
#define INF 0x7fffffff
#define esp 1e-8
int i,j,k;
int n,m;
int main()
{
    cin>>n>>m;
    string s[105];
    map<int,int>mp;
    mp.clear();
    int flag=0;
    int cnt=0;
    string pa;
    for(int i=0; i<n; i++)
    {
        cin>>s[i];
        mp[s[i].size()]++;
        if(mp[s[i].size()]==1)cnt++;
    }
    cin>>pa;
    int len=pa.size();
    if(cnt==1)
    {
        printf("1 %d\n",n+((n-1)/m)*5);
    }
    else {
        int x=n;
        for(int i=len; i<=100; i++)
            x-=mp[i];
        int y=x+mp[len];
        x++;
        printf("%d %d\n",x+((x-1)/m)*5,y+((y-1)/m)*5);
    }
    return 0;
}

C题： c题写了，，但是总是超内存，，其实就是因为剪枝不正确，，，比赛后看了其他人的剪枝方法，，然后加上去，，最后超时了，，最后改为建反向图就A了，，可能是数据卡的比较紧，，，

题目意思就是给你一张有向图，不存在环， n个点，m条边，限定花费T ，输入 m条边的信息，， u v w 从第u到第v所需花费w ，，图中不存在环，，最后让你求从第一个点到第n个点经过点最多且没有超过限定花费的路径，，输出任意一种，，输出第一行一个k代表经过了k个点，第二行输出这k个点，，按顺序输出

一开始想到的是最大流，，但是最后想想不用这么麻烦，，只需bfs暴力搜一遍，，但是中间会有很多重复的路径，当时没想到好的剪枝放发就超内存了，，最后看别人的是用一个数组 vis[][] 表示经过第i个点经过点的个数为j 时所花费的时间，，所以当第二次经过这种状态的点时如果花费大于了之前的花费就可以continue了，，这样就避免了没有必要的计算，，还有人使用dp做的，，也有用dfs做的，，我觉得都可以，，其实仔细想想dfs比bfs好做写，dp不那么好像到，，可能自己菜

代码：

#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<stdio.h>
#include<vector>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define lcr(a,b) memset(a,b,sizeof(a))
#define sfor(i,n) for(i=0;i<n;i++)
#define dfor(i,n) for(i=n-1;i>=0;i--)
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d\n",x)
#define ll long long
#define INF 0x7fffffff
#define esp 1e-8
int n,m,t;
int ans_len;
int hed[5005],e;
vector<int>ans;
struct nood
{
    int u,nex;
    int w;
} nd[5005];
int vis[5005][5005];
struct nod
{
    vector<int>v;
    int len;
    int tm;
    int num;
};
void addedge(int u,int v,int w)
{
    nd[e].u=v,nd[e].w=w,nd[e].nex=hed[u],hed[u]=e++;
}
void bfs(int s)
{
    queue<nod>q;
    nod a,b;
    a.len=1;
    a.v.push_back(s);
    a.tm=0;
    a.num=s;
    q.push(a);
    while(!q.empty())
    {
        a=q.front();
        q.pop();
        int now = a.num;
        for(int i=hed[now]; ~i; i=nd[i].nex)
        {
            b=a;
            int u=nd[i].u;
            if(b.tm+nd[i].w<=t)
            {
                b.tm+=nd[i].w;
                b.len++;
                b.num=u;
                b.v.push_back(u);
                if(vis[u][b.len]==-1||vis[u][b.len]>b.tm)
                {
                    vis[u][b.len]=b.tm;
                }
                else continue;
                if(u==1)
                {
                    if(ans_len==0)
                    {
                        ans=b.v;
                        ans_len=b.len;
                    }
                    else
                    {
                        if(b.len>ans_len)
                        {
                            ans=b.v;
                            ans_len=b.len;
                        }
                    }
                }
                else q.push(b);
            }
        }
    }
}
int32_t main()
{
    while(cin>>n>>m>>t)
    {
        ans.clear();
        ans_len=0;
        memset(hed,-1,sizeof(hed));
        lcr(vis,-1);
        e=1;
        for(int i=0; i<m; i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(v,u,w);
        }
        bfs(n);
        printf("%d\n",ans_len);
        for(int i=ans_len-1; i>=0; i--)
            printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;
}