1
18
2016
0

Diary of OI

Jan.18th

注:黑粗体为超链接
大特判
简单DFS

两个指针记录一下Alice和Bob当前吃到哪里就行 Alice先吃

一开始看上去很不可做……然后发现数据范围非常非常小
那就DFS嘛 :-)
 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Per(x,a,b) for (int x=a;x>=b;x--)
#define ll long long
using namespace std;
inline int IN(){
    int x=0,ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int a,b,n,hp[11],axl[11],cnt[11],Ans=1<<30;
void Hit(int pos){
    cnt[pos]++;
    hp[pos]-=a;
    hp[pos-1]-=b;
    hp[pos+1]-=b;
}
void DontHit(int pos){
    cnt[pos]--;
    hp[pos]+=a;
    hp[pos-1]+=b;
    hp[pos+1]+=b;
}
bool AllKill(){
    Rep(i,2,n) if (hp[i]>=0return 0;
    return 1;
}
void DFS(int cs,int np){
    if (AllKill()){
        if (cs<Ans){
            Ans=cs;
            memcpy(axl,cnt,sizeof cnt);
        }
        return;
    }
    Rep(i,np,n-1if (hp[i]>=0||hp[i-1]>=0||hp[i+1]>=0){
        Hit(i);
        DFS(cs+1,i);
        DontHit(i);
    }
}
int main(){
    n=IN(),a=IN(),b=IN();
    Rep(i,1,n) hp[i]=IN();
    int nc=0;
    while (hp[1]>=0) nc++,Hit(2);
    while (hp[n]>=0) nc++,Hit(n-1);
    DFS(nc,2);
    printf("%d\n",Ans);
    Rep(i,2,n-1while (axl[i]) axl[i]--,printf("%d ",i);
}
用两个单调队列维护就行
 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Per(x,a,b) for (int x=a;x>=b;x--)
#define ll long long
using namespace std;
inline int IN(){
    int x=0,ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int n,k,big[100005],sml[100005],a[100005];
int bt,st,bh,sh,Ans[100005][2];
void Push(int val){
    while (bt>=bh&&val>big[bt]) bt--;big[++bt]=val;
    while (st>=sh&&val<sml[st]) st--;sml[++st]=val;
}
void Pop(int val){
    if (big[bh]==val) bh++;
    if (sml[sh]==val) sh++;
}
int main(){
    n=IN(),k=IN();
    Rep(i,1,n) a[i]=IN();
    int l=1,Max=1,num=1;
    sh=bh=1;
    Push(a[1]);
    Ans[1][0]=Ans[1][1]=1;
    Rep(i,2,n){
        Push(a[i]);
        while (big[bh]-sml[sh]>k) Pop(a[l]),l++;
        if (i-l+1>Max){
            Max=i-l+1;
            num=1;
            Ans[1][0]=l,Ans[1][1]=i;
        }
        else if (i-l+1==Max){
            num++;
            Ans[num][0]=l;
            Ans[num][1]=i;
        }
    }
    printf("%d %d\n",Max,num);
    Rep(i,1,num) printf("%d %d\n",Ans[i][0],Ans[i][1]);
}
暴力枚举每行每列涂不涂就行
标算是很复杂的东西……但这些我们不管
我们模拟退火就行 模拟退火是神器

晚上做了点528给初三爷们的作业……我去试了一下难度1
我这么弱 所以毫无疑问地爆炸了
我用了记忆化搜索
先存一下每个数字出现的次数
fi表示从1~i能获取的最大价值
 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Per(x,a,b) for (int x=a;x>=b;x--)
#define ll long long
using namespace std;
inline int IN(){
    int x=0,ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
ll f[100005];
int n,cnt[100005],Max;
ll DFS(int val){
    if (val<=0return 0;
    if (~f[val]) return f[val];
    f[val]=0;
    if (1ll*cnt[val]*val+DFS(val-2)>f[val]) f[val]=1ll*cnt[val]*val+DFS(val-2);
    if (DFS(val-1)>f[val]) f[val]=DFS(val-1);
    return f[val];
}
int main(){
    n=IN();
    Rep(i,1,n){
        int x=IN();
        cnt[x]++;
        if (x>Max) Max=x;
    }
    memset(f,-1,sizeof f);
    printf("%I64d\n",DFS(Max));
}
存一下每个数字在每个数列中出现的位置
然后枚举一下i和j,其中i是当前第一行要处理的位置,j是之前任意的位置
判断一下每个数列中aj是否都出现在ai前面就行
 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Per(x,a,b) for (int x=a;x>=b;x--)
#define ll long long
using namespace std;
inline int IN(){
    int x=0,ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int n,k,a[5][1000],pos[5][1001],f[1000];
bool Judge(int form,int latt){
    Rep(i,1,k-1if (pos[i][form]>pos[i][latt]) return 0;
    return 1;
}
int main(){
    n=IN(),k=IN();
    Rep(i,0,k-1) Rep(j,0,n-1) a[i][j]=IN(),pos[i][a[i][j]]=j;
    Rep(i,0,n-1){
        f[i]=1;
        Rep(j,0,i-1if (f[j]+1>f[i]) if (Judge(a[0][j],a[0][i])) f[i]=f[j]+1;
    }
    int Ans=0;
    Rep(i,0,n-1if (f[i]>Ans) Ans=f[i];
    printf("%d\n",Ans);
}
记录一下每个位置最长连续上升序列的左端点和右端点
然后枚举断点就行……这种题我WA了9发  凸(艹皿艹 )
Category: Diary | Tags: codeforces | Read Count: 187

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com