2018-3-6-exam

为了写题解刚又把弃置了好久的博客刨了出来。。

T1

哈哈不会,什么AC自动机套DP什么玩意儿不会。

别人家的代码和题解奉上。

T2

能看出来是个高维背包,我交了之后才发现自己的代码根本无法解决同样的人不同的队长的去重问题。
后来看了题解原来排一下序就可以解决这个问题。。

我们定义 $f[i][a][b][c][d][e]$ 表示枚举了前$i$个人之后四种职业的球员各有$a,b,c,d$,且总代价为$e$时的最大收益,$g[i][a][b][c][d][e]$表示同上意义下的方案数,$h[i][a][b][c][d][e]$,同上意义一下不考虑队长时的最优方案的价值最大的人(可以理解为当前方案的队长,只是和一般收益分开统计了)。由于内存爆炸,我们将第一位滚掉然后倒着更新。

首先将所有人照价值大小排序,可以保证当前方案的最后枚举到一个人一定是队长。

然后就是比较长的背包转移了。。。

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <cmath>
# define R register
# define LL long long
# define mod 1000000007
# define N 510

using namespace std;

int n,f[2][6][6][4][1010],g[2][6][6][4][1010],h[2][6][6][4][1010],m,ans1,ans2,ans3;

char s[20];

struct zx{int w,v,p;}a[N];

template <typename T> inline void in(R T& a){
R char c=getchar();R T x=0,f=1;
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c=getchar();
a=x*f;
}

template <typename T> inline void maxx(R T& a,const T b){a<b? a=b:0;}
template <typename T> inline void minn(R T& a,const T b){a>b? a=b:0;}

inline bool cmp(R zx a,R zx b){return a.v < b.v || (a.v == b.v&&a.w > b.w);}

int main(){

freopen("wosa.in","r",stdin);
freopen("wosa.out","w",stdout);

memset(f,-127/3,sizeof(f));
memset(h,-127/3,sizeof(h));
f[0][0][0][0][0] = 0;
g[0][0][0][0][0] = 1;
h[0][0][0][0][0] = 0;

ans1 = -2000101900;

in(n);
for (R int i=1; i<=n; ++i)
{
scanf("%s",s);
if (s[0] == 'G') a[i].p = 0;
else if (s[0] == 'D') a[i].p = 1;
else if (s[0] == 'M') a[i].p = 2;
else a[i].p = 3;
in(a[i].v),in(a[i].w);
}

sort(a+1,a+n+1,cmp);

in(m);

for (R int i=1; i<=n; ++i)
{
R int st[4]={1,5,5,3};
st[a[i].p]--;
for (R int s1=st[0]; s1>=0; --s1)
for (R int s2=st[1]; s2>=0; --s2)
for (R int s3=st[2]; s3>=0; --s3)
for (R int s4=st[3]; s4>=0; --s4)
if (s1+s2+s3+s4<11)
{
for (R int j=m; j>=a[i].w; --j)
{
if (g[s1][s2][s3][s4][j-a[i].w])
{
R int t1=s1,t2=s2,t3=s3,t4=s4;
if (a[i].p == 0) t1++;
else if (a[i].p == 1) t2++;
else if (a[i].p == 2) t3++;
else t4++;
if (f[t1][t2][t3][t4][j] < f[s1][s2][s3][s4][j-a[i].w]+a[i].v)
{
f[t1][t2][t3][t4][j] = f[s1][s2][s3][s4][j-a[i].w]+a[i].v;
g[t1][t2][t3][t4][j] = 0;
h[t1][t2][t3][t4][j] = a[i].v;
}
if (f[t1][t2][t3][t4][j] == f[s1][s2][s3][s4][j-a[i].w]+a[i].v && h[t1][t2][t3][t4][j] < a[i].v)
{
g[t1][t2][t3][t4][j] = 0;
h[t1][t2][t3][t4][j] = a[i].v;
}
if (f[t1][t2][t3][t4][j] == f[s1][s2][s3][s4][j-a[i].w]+a[i].v && h[t1][t2][t3][t4][j] == a[i].v)
{
g[t1][t2][t3][t4][j] += g[s1][s2][s3][s4][j-a[i].w];
minn(g[t1][t2][t3][t4][j],1000000000);
}

}
}
}

}

for (R int s1=3; s1<=5; ++s1)
for (R int s2=2; s2<=5; ++s2)
for (R int s3=1; s3<=3; ++s3)
if (1+s1+s2+s3 == 11)
for (R int i=0; i<=m; ++i)
{
if (g[1][s1][s2][s3][i] == 0) continue;
if (ans1 < f[1][s1][s2][s3][i]+h[1][s1][s2][s3][i])
{
ans1 = f[1][s1][s2][s3][i]+h[1][s1][s2][s3][i];
ans2 = i;
ans3 = 0;
}

if (ans1 == f[1][s1][s2][s3][i]+h[1][s1][s2][s3][i] && ans2 > i)
{
ans2 = i;
ans3 = 0;
}

if (ans1 == f[1][s1][s2][s3][i]+h[1][s1][s2][s3][i] && ans2 == i)
{
ans3 += g[1][s1][s2][s3][i],minn(ans3,1000000000);
}
}

printf("%d %d %d",ans1,ans2,ans3);

return 0;
}

T3

%%%HWB大佬发现了规律。
显然前40%可以用两次矩阵快速幂求到答案,但由于第一次快速幂不能取模导致只能算出90多,在想多拿三十分的话还得勤勤恳恳写个高精出来。
然后答案是循环的。 可以高精打表达出来(循环节太他妈长了我一开始以为不循环呢)。
$k=3*(10^9+7)+6$

$p = 2*(10^9+7)+2$

$f(f(n)) = f(f(n/ mod/ k)/ mod/ p)$

乱搞一下

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
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <cmath>
# define R register
# define LL long long
# define MOD 1000000007LL
const LL M = MOD*6+6;
const LL N = MOD*2+2;

using namespace std;

LL n,a[2][2],ans[2][2];

int T,len;

char s[110];

template <typename T> inline void in(R T& a){
R char c=getchar();R T x=0,f=1;
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c=getchar();
a=x*f;
}

inline void add(R LL& a,const LL b){a+=b; a>=MOD? a-= MOD:0;}

inline void mul(R LL a[2][2],R LL b[2][2]){
R LL c[2][2] = {0};
for (R int i=0; i<=1; ++i)
for (R int j=0; j<=1; ++j)
for (R int k=0; k<=1; ++k)
c[i][j]+=a[i][k]*b[k][j]%N,c[i][j]%=N;
memcpy(a,c,sizeof(c));
}

inline void mulmod(R LL a[2][2],R LL b[2][2]){
R LL c[2][2] = {0};
for (R int i=0; i<=1; ++i)
for (R int j=0; j<=1; ++j)
for (R int k=0; k<=1; ++k)
add(c[i][j],a[i][k]*b[k][j]%MOD);
memcpy(a,c,sizeof(c));
}

int main(){

freopen("na.in","r",stdin);
freopen("na.out","w",stdout);

in(T);
while (T--)
{
scanf("%s",s+1); len = strlen(s+1);
n = 0;
for (R int i=1; i<=len; ++i)
{
n = n*10+s[i]-'0';
n %= M;
}

ans[0][0] = 0, ans[0][1] = 1;
a[0][0] = 0,a[0][1] = a[1][0] = a[1][1] = 1;

while (n)
{
if (n&1LL) mul(ans,a);
mul(a,a);
n >>= 1;
}

n = ans[0][0];

ans[0][0] = 0, ans[0][1] = 1;
a[0][0] = 0,a[0][1] = a[1][0] = a[1][1] = 1;

while (n)
{
if (n&1LL) mulmod(ans,a);
mulmod(a,a);
n >>= 1;
}

printf("%lld\n",ans[0][0]);
}
}

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. T1
  2. 2. T2
  3. 3. T3
,