.N表示宝藏点的个数,day2再随便写点

PID30 / [stupid]弱质的矿工☆

图片 1

自评:

(完毕时间3.5时)

首先题 模拟
就算A了,代码敲得有点慢

其次题 最短路
第三遍敲对了,又考虑数据范围和答案范围,改错了,100分改成42分。QAQ。

图片 2

 

其三题 乱搞 80分
还能(因为没思路啊),不过也有A了的

万一第二题不手贱的话,day1
280分,day2再任由写点,妥妥的头等。

心痛没要是。(也还好不是联赛)。

背景

Stupid

P3392 涂国旗

    • 10通过
    • 267提交
  • 标题提供者kkksc03

  • 标签
  • 难度普及-

 提交  讨论  题解  

家门得知在HYC家的后花园里的宗旨花坛处,往东走3步,向北走3步,再向南走3步,往西走3步,再向南走6步,向北走3步,往西走12步,再向南走2步(

-||)就能找到宝藏的入口,而且宝藏都是藏在山里的,必须挖出来,于是Stupid家族派狗狗指引矿工队去挖宝藏.(HYC家的遗产被狗狗挖走后有怎样感想?)

 

最新研商

描述

本条遗产的创立者为了掩盖世人耳目,他做的财富是从未有过开腔,只有进口,不少构筑宝藏的人都死在里面.今昔精通宝藏总共有N个分岔口,在分岔口处是有财宝的,每个宝藏点都有一个财物值.狗狗只带了M个人来,而且为了安全起见,在每个分岔口,必须至少留一个人下来,这几个留下来的人可以挖宝藏(每个人只好挖一个地方的宝藏),那样才能担保不会迷路,而且以此迷宫有个特性,任意两点间有且只有一条路可通.狗狗为了让他的00快意,决定要硬着头皮地多挖些财富回去.现在狗狗的圈叉电脑不在身旁,只好求助于您了,你要通晓,狗狗的终生幸福就在你手上了..(狗狗ps:00,你不可能就那样屏弃偶……)

标题叙述

某国法律规定,只要一个由N*M个小方块组成的样板符合如下规则,就是合法的国旗。(毛熊:阿嚏——)

  • 从最上方若干行(>=1)的格子全体是反革命的。

  • 接下去若干行(>=1)的格子全部是黑色的

  • 剩余的行(>=1)全体是藏蓝色的

现有一个棋盘状的破布,分成了N行M列的格子,每个格子是反革命灰色红色之一,小a希望把那几个布改成该国国旗,方法是在局地格子上涂颜料,盖住往日的颜色。

小a很懒,希望涂最少的格子,使那块破布成为一个官方的国旗。

输入格式

第1行:五个正整数N,M
.N表示宝藏点的个数,M表示狗狗带去的食指(那是一条懒狗,他自己也好做事)。(n<=1000,m<=100)

第2行:N个整数,第i个整数表示第i个宝藏的财物值.(有限扶助|wi|<maxint)

第N+2行:五个非负整数A和B,表示A通向B,当A=0,表示A是入口.(保障A,B<=n)

输入输出格式

输入格式:

 

率先行是四个整数,N,M

接下去N行是一个矩阵,矩阵的每一个小方块是’W’(白),’B’(蓝),’R’(红)中的一个

 

出口格式:

 

一个平头,表示至少必要涂多少块。

 

出口格式

输出狗狗能带回去的遗产的市值。

输入输出样例

输入样例#1:

4 5
WRWRW
BWRWB
WRWRW
RWBWR

出口样例#1:

11

样例输入

4 3
5 6 2 4
1 2
0 1
2 3
3 4

说明

样例解释:

对象状态是

WWWWW
BBBBB
RRRRR
RRRRR

总共必要改11个格子

对于100%的数据,N,M<=50

100分代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=55;
char mp[N][N],bf[N][N],w[N],b[N],r[N];
int n,m,ans=0x7fffffff;
inline int check(char *a,char *b){
    int res=0;
    for(int i=1;i<=m;i++) if(a[i]!=b[i]) res++;
    return res;
}
void dfs(){
    memcpy(bf,mp,sizeof mp);
    for(int i=1;i<=n-2;i++){
        int tans=0;
        for(int q=1;q<=i;q++){
            tans+=check(mp[q],w);
            memcpy(mp[q],w,sizeof w);
        } 
        for(int j=i+1;j<=n-1;j++){
            int t2=0,t3=0;
            for(int q=i+1;q<=j;q++){
                t2+=check(mp[q],b);
                memcpy(mp[q],b,sizeof b);
            } 
            for(int q=j+1;q<=n;q++){
                t3+=check(mp[q],r);
                memcpy(mp[q],r,sizeof r);
            }
            tans+=t2+t3;
            ans=min(ans,tans);
            for(int q=i+1;q<=n;q++) memcpy(mp[q],bf[q],sizeof bf[q]);
            tans-=t2+t3;
        }
        for(int q=1;q<=n;q++) memcpy(mp[q],bf[q],sizeof bf[q]);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
    for(int i=1;i<=m;i++) w[i]='W';
    for(int i=1;i<=m;i++) b[i]='B';
    for(int i=1;i<=m;i++) r[i]='R';
    dfs();
    printf("%d\n",ans);
    return 0;
}

样例输出

 13

 

P3393 逃离僵尸岛

    • 1通过
    • 119提交
  • 难题提供者kkksc03

  • 标签
  • 难度尚无评定

 提交  讨论  题解  

code

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 using namespace std;
 5 const int MAXN = 1010;
 6 struct Edge{
 7     int to,nxt;
 8 }e[10010];
 9 int c[MAXN],f[MAXN][110],head[MAXN];
10 int n,m,tot;
11 
12 void add_edge(int u,int v)
13 {
14     e[++tot].to = v;e[tot].nxt = head[u];
15     head[u] = tot;
16 }
17 void dp(int u,int t)
18 {
19     if (t<=0) return ;
20     for (int i=head[u]; i; i=e[i].nxt)
21     {
22         int v = e[i].to;
23         for (int k=0; k<m; ++k) 
24             f[v][k] = f[u][k]+c[v];
25         dp(v,m-1);
26         for (int k=1; k<=m; ++k) 
27             f[u][k] = max(f[u][k],f[v][k-1]);
28     }
29 }
30 int main()
31 {
32     scanf("%d%d",&n,&m);
33     for (int i=1; i<=n; ++i)
34         scanf("%d",&c[i]);
35     for (int x,y,i=1; i<=n; ++i)
36     {
37         scanf("%d%d",&x,&y);
38         add_edge(x,y);
39     }
40     dp(0,m);
41     printf("%d\n",f[0][m]);
42     return 0;
43 }

 

摩登商讨

难点叙述

小a住的国家被僵尸侵袭了!小a打算逃离到该国唯一的国际空港逃出那些国家。

该公共N个城市,城市里面有道路相连。一共有M条双向道路。有限帮衬没有自环和重边。

K个城市已经被僵尸控制了,借使不慎闯入就会被感染TAT…所以不可能进来。由其中任意城市经过不领先S条道路就足以抵达的其余城市,就是风雨飘摇城市。换句话说只要某个没有被占城市到某个被占城市不当先s距离,就是摇摇欲坠。

小a住在1号都市,国际空港在N号城市,那两座城市没有被入侵。小a走每一段道路(从一个都会直接抵达此外一个都会)得花一整个白天,所以清晨要住公寓。安全的的城池酒店比较有利要P元,而被危险的城市,饭店要拓展安保措施,所以会变贵,为Q元。所有危险的都市的过夜价格同样,安全的城池也是。在1号都市和N城市,不必要住店。

小a相比较抠门,所以她梦想知道从1号都市到N号城市所急需的小不点儿开支。

输入数据保险存在路线,可以成功逃离。输入数据保险她可以逃离成功。

输入输出格式

输入格式:

 

第一行4个整数(N,M,K,S)

第二行2个整数(P,Q)

接下去K行,ci,表示僵尸侵夺的城池

接下去M行,ai,bi,表示一条无向边

 

出口格式:

 

一个整数表示最低消费

 

输入输出样例

输入样例#1:

13 21 1 1
1000 6000
7
1 2
3 7
2 4
5 8
8 9
2 5
3 4
4 7
9 10
10 11
5 9
7 12
3 6
4 5
1 3
11 12
6 7
8 11
6 13
7 8
12 13

输出样例#1:

11000

说明

图片 3

对于20%数据,N<=50

对于100%数据,2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N – 2, 0 ≦ S ≦
100000

1 ≦ P < Q ≦ 100000

100分代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
inline const int read(){
    register int x=0,f=1;
    register char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
#define ll long long
#define xx first
#define yy second
#define pir pair<int,int>
const int N=2e5+10;
struct node{
    int v,next;
}e[N<<1];
int tot,head[N],js[N],pw[N];
bool vis[N],JS[N];
int n,m,s,k,P,Q;
void add(int x,int y){
    e[++tot].v=y;
    e[tot].next=head[x];
    head[x]=tot;
}
void bfs(int S,int lim){
    int dis[N]={0};
    memset(vis,0,sizeof vis);
    queue<pir>q;
    q.push(make_pair(S,0));
    vis[S]=1;
    while(!q.empty()){
        pir h=q.front();q.pop();
        if(h.yy==lim) continue;
        for(int i=head[h.xx];i;i=e[i].next){
            if(!dis[e[i].v]){
                dis[e[i].v]=dis[h.xx]+1;
                if(!vis[e[i].v]){
                    vis[e[i].v]=1;
                    pw[e[i].v]=Q;
                    q.push(make_pair(e[i].v,dis[e[i].v]));
                }
            }
        }
    }
}
void spfa(){
    ll dis[N];
    memset(dis,127,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int>q;
    q.push(1);
    dis[1]=0;
    vis[1]=1;
    while(!q.empty()){
        int h=q.front();q.pop();
        vis[h]=0;
        for(int i=head[h];i;i=e[i].next){
            int v=e[i].v;
            if(JS[v]) continue;
            if(dis[v]>dis[h]+(ll)pw[v]){
                dis[v]=dis[h]+(ll)pw[v];
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v); 
                }
            }
        }
    }
    printf("%lld\n",dis[n]);
}
int main(){
    n=read(),m=read(),k=read(),s=read();
    P=read(),Q=read();
    for(int i=1;i<=k;i++) js[i]=read();
    for(int i=1,x,y;i<=m;i++) x=read(),y=read(),add(x,y),add(y,x);
    for(int i=1;i<=k;i++) bfs(js[i],s);
    for(int i=1;i<=n;i++) if(!pw[i]) pw[i]=P;pw[n]=0;
    for(int i=1;i<=k;i++) JS[js[i]]=1;
    spfa();
    return 0;
}

P3394 机器人的天地

    • 0通过
    • 97提交
  • 题材提供者kkksc03

  • 标签
  • 难度尚无评定

 提交  讨论  题解  

新式切磋

难题叙述

一个机器人从xoy平面出发,根据给定的程序运行,程序中的一个字母E\S\W\N分别代表机器人向西\南\西\北走1米。我们会付出则一段有N个指令的次序。机器人将接连的举办那段程序K次。从原点初始,机器人每执行完一步,就会在地上做一个符号(原点也留了一个)。现在问,所有程序为止后,有些许个1*1的小方形,其八个极端都被坐上了符号?

输入输出格式

输入格式:

 

先是行三个整数,N,K

率先行是长度为N的字符串,每个字符只会是一个字母E\S\W\N分别表示机器人向东\南\西\北走1米。

 

出口格式:

 

一个平头,表示符合必要的小方格数量

 

输入输出样例

输入样例#1:

6 3
SEENWS

出口样例#1:

6

说明

20% N<=50,K=1;

另外20% k=1

另外20% N<=50

100% N<=100000,0<k<=10^9

80分代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+100;  
struct node{
    int x,y;
    bool operator < (const node a) const {
        if(x==a.x) return y<a.y;
        return x<a.x;
    }
    bool operator == (const node a) const{
        return x==a.x&&y==a.y;
    }
    bool operator != (const node a) const{
        return x!=a.x||y!=a.y;
    }
}ans[N<<4];
char s[N];
int cnt,res,n,k;
bool vis[3010][3010];
node deal(int sx,int sy){
    ans[++cnt]=(node){sx,sy};
    int len=strlen(s);
    for(int i=0;i<len;i++){
        if(s[i]=='N') ans[++cnt]=(node){++sx,sy};
        else if(s[i]=='S') ans[++cnt]=(node){--sx,sy};
        else if(s[i]=='W') ans[++cnt]=(node){sx,--sy};
        else if(s[i]=='E') ans[++cnt]=(node){sx,++sy};
    }
    node t;
    t.x=sx;
    t.y=sy;
    return t;
}
int ef(node x){
    int l=1,r=cnt;
    while(l<r){
        int mid=l+r>>1;
        if(x<ans[mid]||ans[mid]==x) r=mid;
        else l=mid+1;
    }
    return l;
}
int solve(){
    sort(ans+1,ans+cnt+1);
    cnt=unique(ans+1,ans+cnt+1)-(ans+1);
    for(int i=1;i<=cnt;i++){
        if(!vis[ans[i].x+1500][ans[i].y+1500]){
            node la=(node){ans[i].x,ans[i].y+1};
            node ra=(node){ans[i].x-1,ans[i].y};
            node aa=(node){ans[i].x-1,ans[i].y+1};
            int lp=ef(la);
            if(ans[lp]!=la) continue;
            int rp=ef(ra);
            if(ans[rp]!=ra) continue;
            int pp=ef(aa);
            if(ans[pp]!=aa) continue;
            res++;
            vis[ans[i].x+1500][ans[i].y+1500]=1;
        }
    }
}
int main(){
    scanf("%d%d%s",&n,&k,s);
    node t=deal(0,0);
    solve();
    int r1=res;
    if(k==1){printf("%d",res);return 0;}
    else{
        deal(t.x,t.y);
        solve();
        int r2=res-r1;
        printf("%lld\n",(ll)r1+(ll)r2*(ll)(k-1));
        //cout<<(ll)r1+(ll)r2*(ll)(k-1);
    }
    return 0;
}

 改后的AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
struct node{
    int x,y;
    bool operator < (const node& a)const{
        return x<a.x||(x==a.x&&y<a.y);
    }
};
set<node>S;
long long n,k,ans,lr,r;
char s[100010];
int main(){
    scanf("%d%d%s",&n,&k,s);
    node now;
    now.x=0;now.y=0;
    S.insert(now);
    for(int i=1;i<=k;i++){
        r=0;
        for(int j=0;j<n;j++){
            if(s[j]=='E')now.y++;
            if(s[j]=='W')now.y--;
            if(s[j]=='S')now.x--;
            if(s[j]=='N')now.x++;
            if(S.count(now)==0){
                node a,b,c,d,e,f,g,h;
                a.x=now.x-1;a.y=now.y-1;b.x=now.x-1;b.y=now.y;
                c.x=now.x-1;c.y=now.y+1;d.x=now.x;d.y=now.y-1;
                e.x=now.x;e.y=now.y+1;f.x=now.x+1;f.y=now.y-1;
                g.x=now.x+1;g.y=now.y;h.x=now.x+1;h.y=now.y+1;
                if(S.count(a)==1&&S.count(b)==1&&S.count(d)==1)r++;
                if(S.count(b)==1&&S.count(c)==1&&S.count(e)==1)r++;
                if(S.count(d)==1&&S.count(f)==1&&S.count(g)==1)r++;
                if(S.count(e)==1&&S.count(g)==1&&S.count(h)==1)r++;
                S.insert(now);
            }
        }    
        if(r==lr){
            ans+=(k-i+1)*r;
            break;
        }
        ans+=r;lr=r;
    }
    cout<<ans<<endl;
    return 0;
}

 

相关文章