除了F题都比较水吧。。F题Div2只有一个在结束之前2minAC的。。
A
1 | //Code by Lucida |
B
写完E题回来看发现有个细节可能被hack，改掉交上之后从rnk30直接rnk100。。好吧，关键是比赛之后交之前的版本居然A了，，感觉非常。。。
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//Code by Lucida
typedef long long ll;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
int divider;
bool check(char *s,int S,int n)
{
ll x=0;
int i=0;
while(i<=n && !((S>>i)&1)) i++;
if(s[i]=='0' || i>=n) return 0;
for(;i<=n;++i)
if((S>>i)&1)
(x*=10)+=s[i]-'0';
return x%divider==0;
}
int popcount(int S)
{
int cnt=0;
while(S)
{
cnt++;
S-=(S & -S);
}
return cnt;
}
int main()
{
char n[100];scanf("%s",n);
int k;get(k);
int len=strlen(n);
int Ans=len-1;
divider=1;
for(int i=1;i<=k;++i) divider*=10;
for(int S=(1<<len)-1;~S;S--)
{
//printf("%d\n",S);
if(check(n,S,len))
chkmn(Ans,len-popcount(S));
}
put(Ans),putchar('\n');
return 0;
}
C
1 | //Code by Lucida |
D
二分答案。。。
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//Code by Lucida
typedef long long ll;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=200000+11;
char s[MAXN],t[MAXN];
int opt[MAXN],ns,nt;
bool check(int step)
{
static int us[MAXN],ut;
++ut;
for(int i=1;i<=step;++i) us[opt[i]]=ut;
for(int i=1,j=1;i<=ns;++i)
{
if(us[i]==ut) continue;
if(s[i]==t[j]) j++;
if(j==nt+1) return 1;
}
return 0;
}
int main()
{
scanf("%s",s+1);
scanf("%s",t+1);
ns=strlen(s+1),nt=strlen(t+1);
for(int i=1;i<=ns;++i) get(opt[i]);
int L=0,R=ns;
while(L!=R)
{
int Mid=(L+R+1)>>1;
if(check(Mid)) L=Mid;
else R=Mid-1;
}
put(L),putchar('\n');
return 0;
}
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//Code by Lucida
typedef long long ll;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::string;
using std::map;
using std::cin;
using std::cout;
using std::bitset;
const int MAXN=5000+11,MAXBIT=1e3+11;
struct Var
{
int a,b;char opt;
bitset<MAXBIT> num;
}var[MAXN];
map<string,int> ref;
string name[MAXN];
void b2t(string s,bitset<MAXBIT> &b)
{
for(unsigned int i=0;i<s.size();++i)
b[i]=s[i]-'0';
}
int us[MAXN],ut;
bool calc(int i,int b)
{
static bool val[MAXN];
if(us[i]==ut) return val[i];
us[i]=ut;
if(var[i].opt==0)
return val[i]=var[i].num[b];
else
{
switch(var[i].opt)
{
case 'A':val[i]=calc(var[i].a,b) & calc(var[i].b,b);break;
case 'O':val[i]=calc(var[i].a,b) | calc(var[i].b,b);break;
case 'X':val[i]=calc(var[i].a,b) ^ calc(var[i].b,b);break;
}
return val[i];
}
}
int n;
int count(bool v,int b)
{
++ut;
var[0].num[b]=v;
int cnt=0;
for(int i=1;i<=n;++i)
cnt+=calc(i,b);
return cnt;
}
int main()
{
ref["?"]=0;
int m;get(n),get(m);
string opt;
for(int i=1;i<=n;++i)
{
cin>>name[i];
ref[name[i]]=i;
cin>>opt>>opt;
if(isdigit(opt[0]))
{
b2t(opt,var[i].num);
var[i].opt=0;
}
else
{
var[i].a=ref[opt];
cin>>opt;
var[i].opt=opt[0];
cin>>opt;
var[i].b=ref[opt];
}
}
static char mx[MAXBIT],mn[MAXBIT];
for(int i=m-1;~i;--i)
{
int c0=count(0,i),c1=count(1,i);
if(c0==c1) mx[i]=mn[i]='0';
else if(c0>c1) mx[i]='0',mn[i]='1';
else if(c0<c1) mn[i]='0',mx[i]='1';
else assert(0);
}
puts(mn),puts(mx);
return 0;
}
F
研究了zky大神的代码好长时间才差不多明白(人弱求不D)
思路大概是Trie的合并
枚举每个点，把这个点的子节点的Trie合并起来，看合并之后的子树大小。同一层的合并一定是互不影响的。
胡扯一下复杂度？
最坏情况是每次都要合并，合并的最坏复杂度是)所以
求教复杂度。。。。
还有其他做法啊。。待学习。。
Code
1 | //Code by Lucida |
这样可以把三角划分转化为划分序列连乘顺序
序列连乘顺序可以转化为合法括号序列数目
然后就可以解决了