Wannafly Winter Camp 2020-Day2

真的隔了好久才补 赛时爆零了qwq

2A. 托米的字符串

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
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(ll i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 5;
char s[maxn];
double p[maxn],q[maxn],ans;
int judge(char c){
if(c=='a'||c=='e'||c=='i') return 1;
if(c=='o'||c=='u'||c=='y') return 1;
return 0;
}
int main(){
scs(s+1); int len=strlen(s+1);
rep(i,1,len+1) p[i]=p[i-1]+1.0/i;
rep(i,1,len+1) q[i]=q[i-1]+p[i];
rep(i,1,len+1) if(judge(s[i]))
ans+=q[len]-q[len-i]-q[i-1];
pf("%.9lf\n",2.0*ans/(1.0*len*(len+1)));
}

2C. 纳新一百的石子游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(ll i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
ll x,q[65];
int main(){
int n; sc(n); rep(i,0,n){
ll a; scl(a); x^=a; int cnt=0; while(a){
cnt++; if(a&1) q[cnt]++; a>>=1;
} if(!x) pf("0\n"); else{
cnt=0; ll x1=x; while(x1){
cnt++; x1>>=1;
} pf("%d\n",q[cnt]);
}
}
}

2K. 破忒头的匿名信

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
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
char s[maxn];
ll tot,ch[maxn][26],nex[maxn];
ll len[maxn],val[maxn],f[maxn];
void insert(char* s,ll x){
int n=strlen(s+1),p=1;
rep(i,1,n+1){
int tmp=s[i]-'a';
if(!ch[p][tmp]) ch[p][tmp]=++tot,len[tot]=len[p]+1;
p=ch[p][tmp];
} if(!val[p]) val[p]=x;
else val[p]=min(val[p],x);
}
void build(){
queue<ll>q; q.push(1); nex[1]=0;
while(!q.empty()){
int fr=q.front(); q.pop();
rep(i,0,26) if(!ch[fr][i]) ch[fr][i]=ch[nex[fr]][i];
else nex[ch[fr][i]]=ch[nex[fr]][i],q.push(ch[fr][i]);
}
}
int find(char* s){
int n=strlen(s+1),p=1; rep(i,1,n+1){
int tmp=s[i]-'a',k=ch[p][tmp]; while(k>1){
if(val[k]) f[i]=min(f[i],f[i-len[k]]+val[k]); k=nex[k];
} p=ch[p][tmp];
} if(f[n]>1e18) return puts("-1"); return pf("%lld\n",f[n]);
}
int main(){
ll n,a; scl(n); mst(f,0x3f); f[0]=0;
rep(i,0,26) ch[0][i]=1; tot=1;
rep(i,0,n) scs(s+1),scl(a),insert(s,a);
build(); scs(s+1); find(s);
}