普及T1 明明的随机数
排序去重即可。
1 |
|
普及T2 开心的金明
最基本的01背包。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int V, n, f[30005] = {0}, v[30], w[30];
void init(){
V = read(), n = read();
for(int i = 0; i < n; ++i)
v[i] = read(), w[i] = read();
}
void solve(){
for(int i = 0; i < n; ++i)
for(int j = V; j >= v[i]; --j)
f[j] = max(f[j], f[j - v[i]] + w[i] * v[i]);
printf("%d\n", f[V]);
}
int main(){
init();
solve();
return 0;
}
普及T3 Jam的计数法
自己手写一个生成下一个组合的函数。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int s, t, l;
char p[30];
void init(){
s = read() - 1, t = read() - 1, l = read();
scanf("%s", p);
for(int i = 0; i < l; ++i)
p[i] -= 'a';
}
bool getC(){
int cur = l - 1;
while(cur >= 0 && p[cur] == t - l + 1 + cur)
cur--;
if(cur == -1)
return false;
p[cur]++, cur++;
while(cur < l)
p[cur] = p[cur - 1] + 1, cur++;
for(int i = 0; i < l; ++i)
putchar(p[i] + 'a');
putchar('\n');
return true;
}
void solve(){
for(int i = 0; i < 5; ++i)
if(!getC())
break;
}
int main(){
init();
solve();
return 0;
}
普及T4 数列
容易证明
令可以推出
随着$N$递增。
而$N$从$1$开始增加，因此该数列的第$N$项即为上式。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n,k,m=0,s=0;
int p(int w){
int res=1;
for(int i=1;i<=w;i++)res*=n;
return res;
}
int main(){
scanf("%d%d",&n,&k);
while(k){
if(k&1)s+=p(m);
m++,k>>=1;
}
printf("%d\n",s);
return 0;
}
提高T1 能量项链
和石子合并差不多。
由于是环状，所以需要把原来的项链复制一遍。
很经典的区间DP。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
using namespace std;
int dp[205][205]={0},n,dat[205][2];
int main(){
scanf("%d",&n);
n<<=1;
int _n=n;
for(int i=0;i<_n;i++)
scanf("%d",&dat[i][0]),
dat[i+_n][0]=dat[i][0];
dat[n-1][1]=dat[0][0];
for(int i=0;i<n-1;i++)
dat[i][1]=dat[i+1][0];
for(int i=1;i<_n;i++)//i:length
for(int j=0;j+i<n;j++)
for(int k=j;k<i+j;k++)
dp[j][i+j]=max(dp[j][j+i],dp[j][k]+dp[k+1][i+j]+
dat[j][0]*dat[k][1]*dat[i+j][1]);
int ans=dp[0][_n-1];
for(int i=1;i<_n;i++)
ans=max(ans,dp[i][i+_n-1]);
printf("%d\n",ans);
return 0;
}
提高T2 金明的预算方案
一个很不寻常的背包DP。
由于有附件的存在，我们需要将购买不同的附件相分开。
即将购买0到多个附件分别作为不同的决策考虑。
由于附件数不超过2个，所以我们购买某一个主件和其附件的时候至多只有4种决策：只购买主件，或者买主件和两个附件中的一个，或者主附件全买。
这样的话就归化成了一个普通的01背包问题。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
using namespace std;
int dp[32005]={0},n,W,w[62][5]={0},v[62][5]={0};
int main(){
scanf("%d%d", &W, &n);
for(int i = 1; i <= n; ++i){
int j, p, k;
scanf("%d%d%d", &j, &p, &k);
if(k){
if(w[k][0] > 1)
w[k][3] += j, w[k][4] += j, w[k][0] += 2,
v[k][3] += p * j, v[k][4] += p * j;
else
w[k][2] += j, w[k][3] += j, w[k][0]++,
v[k][3] += p * j, v[k][2] += p * j;
}else{
w[i][0]++, w[i][1] += j, w[i][2] += j, w[i][3] += j, w[i][4] += j;
v[i][3] += p * j, v[i][4] += p * j, v[i][1] = p * j, v[i][2] += p * j;
}
}
for(int i = 1; i <= n; ++i)
if(w[i][0])
for(int j = W; j >= w[i][1]; --j)
for(int k = 1; k <= w[i][0]; ++k)
if(j - w[i][k] >= 0)
dp[j] = max(dp[j], dp[j - w[i][k]] + v[i][k]);
printf("%d\n", dp[W]);
return 0;
}
提高T3 作业调度方案
模拟即可…
千万不要考虑什么奇奇怪怪的优化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
using namespace std;
typedef struct{
int gid,_id,p[2];
}Move;
Move move[405],*pt[25][25];
int mac[25][455]={0},cnt[25]={0},m,n;
int ok(int id,int l,int r){
for(int i=l;i<=r;i++)
if(mac[id][i])return i;
for(int i=l;i<=r;i++)
mac[id][i]=1;
return 0;
}
int solve(){
int i,j,k,u,v,id,ans=0;
fill(cnt,cnt+24,1);
for(i=1;i<=m*n;i++){
u=move[i].p[0],v=move[i].p[1],
id=move[i].gid;
for(j=cnt[id];;){
k=ok(u,j,j+v-1);
if(!k){cnt[id]=j+v;break;}
else j=k+1;
}
}
for(i=1;i<=n;i++)
ans=max(ans,cnt[i]);
return ans-1;
}
int main(){
scanf("%d%d",&m,&n);
int i,j,k;
for(i=1;i<=m*n;i++)
scanf("%d",&j),
move[i].gid=j,
move[i]._id=++cnt[j],
pt[j][cnt[j]]=&move[i];
for(k=0;k<2;k++)
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&pt[i][j]->p[k]);
printf("%d\n",solve());
return 0;
}
提高T4 $2^k$进制数
组合数问题。
数码递增视为一个组合。
这样一个数，数码只有$\mathcal 2^k-1$个，故长度至多为$\mathcal 2^k-1$。
因此当$\mathcal w \ge \left(2^k-1\right) \times k $的时候，多出的那部分没有意义。此时令$\mathcal w = \left(2^k-1\right) \times k $。
对于一个$\mathcal w$，一个$\mathcal 2^k$进制数除去最高位至多有$\mathcal \lfloor \frac {w}{k} \rfloor$位。
考虑$\mathcal 2$到$\mathcal \lfloor \frac {w}{k} \rfloor$位，由于数码有$\mathcal 2^k-1$个，故此部分答案为
考虑最高位，由于最高位可能的最大数我们可以算出，设其为$\mathcal u$，则
最高位已经确定，剩下的只有$\mathcal \lfloor \frac {w}{k} \rfloor$个数字要选，备选的数字有$\mathcal 2^k-1-o \left( 1\le o \le u\right)$个，故此部分答案为
两部分相加即为本题答案。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
using namespace std;
int c[520][25],ans[56]={0},k,w,k1,k2;
void mul(int s1[],int s2,int to[]){
to[0]=s1[0];
int x=0;
for(int i=1;i<=s1[0];i++)
x+=s1[i]*s2,to[i]=x%p,x/=p;
for(;x>0;)to[++to[0]]=x%p,x/=p;
for(;to[0]>1&&to[to[0]]==0;)to[0]--;
}
void add(int s1[],int s2[]){
s2[0]=max(s1[0],s2[0]);
int x=0;
for(int i=1;i<=s2[0];i++)
x+=s1[i]+s2[i],s2[i]=x%p,x/=p;
for(;x!=0;)s2[++s2[0]]=x%p,x/=p;
}
void divide(int s1[],int s2){
int x=0;
for(int i=s1[0];i>=1;i--){
x=x*p+s1[i],s1[i]=x/s2,x%=s2;
}
for(;s1[0]>1&&s1[s1[0]]==0;)s1[0]--;
}
void C(int m,int n){
c[0][0]=c[0][1]=1;
for(int i=1;i<=m;i++)
mul(c[i-1],n-i+1,c[i]),divide(c[i],i);
}
int output(int big[]){
printf("%d",big[big[0]]);
for(int i=big[0]-1;i>=1;i--)
printf("%04d",big[i]);
printf("\n");
}
int main(){
scanf("%d%d",&k,&w);
k1=1<<k;
if(w>k*(k1-1))w=k*(k1-1);
C(w/k,k1-1);
for(int i=2;i<=w/k;i++)add(c[i],ans);
k2=1<<(w%k);
for(int i=1;i<k2;i++)
C(w/k,k1-1-i),add(c[w/k],ans);
output(ans);
return 0;
}