ZROIDay3-比赛解题报告
瞎扯
从今天开始考试有点不在状态,可能是因为不太适应题目的原因,T1已经接近了思想但是没有想到状态转移，T2思考方向错误，T3不会打LCT,还是太菜了
A
考场上想到要么不用亵渎要么最后用亵渎，如果最后用亵渎就要满足所有随从血量是从1一直到某个数x的不下降连续序列，于是可以状态转移$f[i][j]$表示前i小的数变成$[1,j]$每一个整数的最小代价,那么我们枚举第i-1小的数是j-1还是j就好了。最后对所有$f[n][i]$取min就好了.当然还要考虑不用亵渎的情况，这个就非常好处理
代码：
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
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#define ll long long
#define ri register int
using std::min;
using std::sort;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=5005;
const ll inf=1e18-1;
ll f[maxn][maxn],a[maxn];
ll ans=0;
ll p,q,r;
int n;
ll cost(ll x,ll y){
if(x>y)return (x-y)*q;
return (y-x)*p;
}
int main(){
read(n);
for(ri i=1;i<=n;i++){
read(a[i]);
}
sort(a+1,a+1+n);
read(p),read(q),read(r);
a[0]=0;
for(ri i=0;i<=n;i++){
ans+=q*a[i];
for(ri j=0;j<=n;j++){
f[i][j]=inf;
}
}
f[0][0]=0;
for(ri i=1;i<=n;i++){
for(ri j=1;j<=i;j++){
f[i][j]=min(f[i][j],min(f[i-1][j],f[i-1][j-1])+cost(a[i],j));
}
}
for(ri i=1;i<=n;i++)ans=min(ans,f[n][i]+r);
printf("%lld\n",ans);
return 0;
}
|
B
这题主要是思路没想到,我们把两个相邻的字符断开，这样原串就变成了许多段，显然我们想要的就是段中的一部分，但是糟糕的是头尾两个字符相同也不行。然后容易发现，我们用KMP求出fail数组，按照定义易知，$i-fail[i]+1$与第一个字符是相同的，于是我们对每一条段跑KMP记录可行答案就好了。然而按这个思路做前面小数据都WA了。。。也不知道怎么回事
代码:
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
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cctype>
#include <cmath>
#define ll long long
#define ri register int
using namespace std;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=2000005;
const int inf=0x7fffffff;
char a[maxn],b[maxn];
bool ok[maxn],ans[maxn];
int fail[maxn],tot=0,len=0;
inline void solve(){
int x,y;
for(ri i=1;i<=tot;i++)fail[i]=0,ok[i]=1;
for(ri i=2,j=0;i<=tot;i++){
while(j&&b[i-1]!=b[j])j=fail[j];
if(b[i-1]==b[j])j++;
fail[i]=j;
}
for(ri i=fail[tot];i;i=fail[i])ok[tot-i+1]=0;
for(ri i=1;i<=tot;i++)if(ok[i])ans[i]=1;
return ;
}
int main(){
int T;
while(scanf("%s",a+1)!=EOF){
T++;
printf("Case %d:",T);
len=strlen(a+1);
for(ri i=1;i<len;i++)a[len+i]=a[len];
len=(len<<1)-1,tot=0;
for(ri i=1;i<=len;i++){
b[tot++]=a[i];
if(a[i]==a[i+1]){
solve();
tot=0;
}
}
solve();
len=(len+1)>>1;
for(ri i=0;i<len;i++){
printf("%d",ans[len-i]);
}
puts("");
memset(ans,0,sizeof(ans));
}
return 0;
}
|
C
不会LCT，太菜了