noip 2015

  • P2615 神奇的幻方
  • P2661 信息传递
  • P2668 斗地主
  • P2678 跳石头
  • P2679 子串
  • P2680 运输计划

    P2615 神奇的幻方

    //p的代码太丑了,不放了

    * P2661 信息传递

    题目地址: https://www.luogu.org/problem/show?pid=2661
    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
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    /*
    ID: redbag
    PROG: 1
    LANG: C++
    */
    #include<set>
    #include<map>
    #include<list>
    #include<queue>
    #include<stack>
    #include<string>
    #include<math.h>
    #include<time.h>
    #include<vector>
    #include<bitset>
    #include<memory>
    #include<utility>
    #include<stdio.h>
    #include<sstream>
    #include<iostream>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    #define LL unsigned long long
    using namespace std;
    int n,i,mi;//mi:min
    int sum;
    int b[200001];//前驱结点
    int a[200001];//编号
    bool f[200001];//是否搜过
    void dfs(int s,int t,int q)//s:轮数,t:目前搜的人的编号,q:出发地
    {
    if (s>=mi) return;//已经超过目前的min了就没有意义再走了
    f[t]=true;//点t到此一游
    if (t==q)//形成环了
    {
    if (s<mi) mi=s;//和min比较
    return;//退出
    } else
    if (!f[a[t]])//没搜过
    {
    b[a[t]]=t;
    dfs(s+1,a[t],q);
    } else//如果下一个点走过,那么在这轮搜索中间一定出现了环
    //或者上一轮搜过那个点, 继续搜的结果和之前搜的一样
    {
    int l=2;//环的长度
    int k=t;//往前找环
    while (b[k]&&b[k]!=a[t])//本轮中有前驱且暂时没和a[t]形成环
    {
    k=b[k];
    l++;
    }
    if (b[k]&&l<mi) mi=l;
    }
    }
    int main()
    {
    mi=200000;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for (i=1;i<=n;i++)
    {
    if (!f[i]&&!f[a[i]])//没搜过
    {
    memset(b,0,sizeof(b));//前驱结点清零
    b[a[i]]=i;//记录前缀
    f[i]=true;//标记
    dfs(1,a[i],i);
    }
    }
    printf("%d",mi);
    return 0;
    }

* P2668 斗地主

感觉这种很简洁

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
int T,n,X,Y;
int a[26],sum;
int d[25];
void dfs(int x)
{
if (x>sum) return;
int ans=0;
for (int i=0;i<5;i++) d[i]=0;
for (int i=0;i<=14;i++) d[a[i]]++;
while (d[4])//不包括顺子的时候贪心的打
{
d[4]--;ans++;
if (d[2]>=2) d[2]-=2; else if (d[1]>=2) d[1]-=2;
}
while (d[3])
{
d[3]--;ans++;
if (d[2]>=1) d[2]--; else if (d[1]>=1) d[1]--;
}
ans+=d[1]+d[2];
if (a[0]&&a[1]&&d[1]>=2) ans--;//大王小王一起打
sum=min(sum,ans+x);
int i,j;
for (i=3;i<15;++i)//各种顺子
{
for (j=i;j<=15;++j)
if (a[j]>=1)
{
a[j]--;if (j-i+1>=5) dfs(x+1);
} else break;
while (j>i) a[--j]++;//回溯
}

for (i=3;i<15;++i)
{
for (j=i;j<=15;++j)
if (a[j]>=2)
{
a[j]-=2;if (j-i+1>=3) dfs(x+1);
} else break;
while (j>i) a[--j]+=2;
}

for (i=3;i<15;++i)
{
for (j=i;j<=15;++j)
if (a[j]>=3)
{
a[j]-=3;if (j-i+1>=2) dfs(x+1);
} else break;
while (j>i) a[--j]+=3;
}
return;
}
int main()
{
T=read();
n=read();
while (T--)
{
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++)
{
X=read();Y=read();
if (X==1) X=14;
if (X==0&&Y==2) X++;//双王的打法只有一起打,单打,4带2,3带1
a[X]++;//大王小王要分开
}
sum=n;
dfs(0);
printf("%d\n",sum);
}
return 0;
}

* P2678 跳石头

题目地址: https://www.luogu.org/problem/show?pid=2678

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
62
63
64
65
#include<set>  
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
//const double pi=acos(-1.0);
int l,m,n,i,aa;
int a[50002],b[50002];
cin>>l>>n>>m;
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
a[n+1]=l;
//a[0]=0;
int y=l;
int x=1;
for (i=n+1;i>=1;i--)
{
a[i]=a[i]-a[i-1];
}
while (x<y)
{
int mid=(x+y+1)/2;
int sum=0;
for (i=1;i<=n+1;i++)
{
b[i]=a[i];
}
for (i=1;i<=n+1;i++)
{
if (b[i]<mid)
{
sum++;
b[i+1]=b[i]+b[i+1];
}
}
if (sum>m)
{
y=mid-1;
} else
{
x=mid;
}
}
cout<<x;
return 0;
}

* P2679 子串

题目地址 https://www.luogu.org/problem/show?pid=2679
$f[k][i][j]$→A串第i个构成B串的第j个字符的方案数【A串中第i个必须构成B串第j个】,所以若$s1[i]<>s2[j]$,那么$f[k][i][j]=0$。

那么让我们来推推$s1[i]==s2[j$]动态转移方程:

① $S1[i-1]<>s2[j-1]$时,A串中的第i个只能独立开辟一个新的子串,此时$i$匹配$j$单独开辟第$k$个子串,所以就是A串$1$~$i-1$匹配到B串$j-1$个时已开辟了$k-1$个子串的所有方案数之和

② $S1[i-1]=s2[j-1]$ 时,除了A串的第i个可以独立开辟一个新的子串外,还可以与第$i-1$相连,继续在前面子串的基础上加,并不独立开辟一个新的子串,此时$i$匹配$j$继续使用第$k$个子串(接上去),所以是$i-1$匹配$j-1$时已经开辟了第k个子串,即 $f[k][i-1][j-1]$。

在记录和的时候可以优化一下,用tmp[j-1]记录 $f[k-1][l][j-1]$的和,在每次做的时候

$tmp[j-1]=tmp[j-1]+f[k-1][i-1][j-1]$即可。【可以到后面代码里慢慢理解】

初始化时由于只有A串中第0项可以匹配B串中的第0项,开辟0个子串,所以$f[0][0][0]=1$即可

第一维由于只需要用当前$k$和前一个$k-1$,所以只用开辟两个就够用了,每次把$k-1$的存储到$f[0]$里去,再操作$f[1]$即可。

其实yz已经说得够清楚的了。

于是我就丢代码了。

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
62
63
64
65
66
67
68
69
70
/*
ID: ylx14271
PROG: noip2015day2t2
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
string sa,sb;
int n,m,k,l,k1,i,j,sum;
int f[2][1010][210];
int t[210];
//k:sb目前搜到的位置
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int mo=1000000007;
cin>>n>>m>>k;
cin>>sa>>sb;//读入
f[0][0][0]=1;
sa=" "+sa;
sb=" "+sb;
k1=0;
do
{
k1++;//子串个数
for (i=0;i<=n;i++)
for (j=0;j<=m;j++)
f[1][i][j]=0;
for (i=0;i<=m+1;i++) t[i]=0;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
t[j-1]=(f[0][i-1][j-1]+t[j-1])%mo;//t[j-1]存和
if (sa[i]==sb[j])
{
f[1][i][j]=t[j-1];//开辟一个新集合
if (i>1&&j>1&&sa[i-1]==sb[j-1])//可以不开辟新集合
{
f[1][i][j]=(f[1][i][j]+f[1][i-1][j-1]) % mo;
}
}
}
for (i=0;i<=n;i++)
for (j=0;j<=m;j++)
f[0][i][j]=f[1][i][j];
}while (k1!=k);
sum=0;
for (i=1;i<=n;i++) sum=(sum+f[0][i][m])%mo;
cout<<sum;
return 0;
}

* P2680 运输计划

(没写)