20230702
今天回来主要打了牛客的周赛
感觉就是DIV4水平，但是自己回寝室都八点了打了半个小时就结束了，实际上多个10min就AK了。
牛客周赛 牛客周赛 Round 1
A
题目大意：画一个大小为 n 的 ‘u’
直接模拟即可：
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
| #include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n*3;i++)
{
for(int j=1;j<=n;j++) cout<<'*';
for(int j=1;j<=2*n;j++) cout<<'.';
for(int j=1;j<=n;j++) cout<<'*';
cout<<'\n';
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++) cout<<'.';
for(int j=1;j<=n;j++) cout<<"*";
for(int j=1;j<=2*(n-i);j++) cout<<".";
for(int j=1;j<=n;j++) cout<<"*";
for(int j=1;j<=i;j++) cout<<'.';
cout<<'\n';
}
return 0;
}
|
B
游游拿到了一个数组，其中一些数被染成红色，一些数被染成蓝色。
游游想知道，取两个不同颜色的数，且它们的数值相等，有多少种不同的取法？
直接两个 map 即可
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200200;
int ans=0;
int n;
int tot,a[maxn];
int val[maxn];
map <int,int> c1,c2;
int col[maxn];
signed main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>val[i];
for(int i=1;i<=n;i++)
{
char tmp;
cin>>tmp;
if(tmp=='R') c1[val[i]]++;
else c2[val[i]]++;
}
for(auto &v:c1)
{
ans+=v.second*c2[v.first];
}
cout<<ans<<endl;
return 0;
}
|
C
游游拿到了一个01串（仅由字符’0’和字符’1’构成的字符串）。游游每次操作可以交换两个相邻的字符，例如，对于字符串"11001"而言，游游可以交换第二个字符和第三个字符变成"10101"。
考虑所有的情况，因为题目保证有解，如果 1 的个数为奇数个，并且 n 的为偶数个，那么一定是 10101 类似的情况，或者偶数个 1 以及 n 为奇数，一定是 01010 类似的情况
如果n为偶数的情况，那就有两种情况 010101 或者 101010 这两种情况，需要分别讨论。
显然不发生交叉的时候是最优的情况，因此我们直接按顺序移动 1 即可。
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200200;
string s;
int n;
int place[maxn],cnt;
int ans;
signed main()
{
ios::sync_with_stdio(false);
cin>>s;
n=s.size();
for(int i=1;i<=n;i++)
{
if(s[i-1]=='1') place[++cnt]=i;
}
ans=n*n;
if(n%2==0)
{
int tans=0;
for(int i=1;i<=n/2;i++)
{
int nowplace=i*2;
tans+=abs(place[i]-nowplace);
}
ans=tans;tans=0;
for(int i=1;i<=n/2;i++)
{
int nowplace=i*2-1;
tans+=abs(place[i]-nowplace);
}
ans=min(ans,tans);
cout<<ans<<endl;
}
else
{
if(cnt==n/2)
{
int tans=0;
for(int i=1;i<=n/2;i++)
{
int nowplace=i*2;
tans+=abs(place[i]-nowplace);
}
cout<<tans<<endl;
}
else
{
int tans=0;
for(int i=1;i<=n/2+1;i++)
{
int nowplace=i*2-1;
tans+=abs(place[i]-nowplace);
}
cout<<tans<<endl;
}
}
return 0;
}
|
D
给你一个数字串，询问有多少字串是9的倍数，可以包含前导0
这个就是记录 f[x] 表示当前模 9 余 x 的方案数，转移方程很简单。
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200200;
const int modp=1e9+7;
string s;
int n;
int f[20],c[20];
signed main()
{
ios::sync_with_stdio(false);
cin>>s;
n=s.size();
for(int i=1;i<=n;i++)
{
char tmp=s[i-1];
int v=tmp-'0';
for(int j=0;j<=8;j++) c[j]=0;
for(int j=0;j<=8;j++)
{
c[(j+v)%9]=(f[j]+f[(j+v)%9])%modp;
}
for(int j=0;j<=8;j++) f[j]=c[j];
f[v%9]=(f[v%9]+1)%modp;
}
cout<<f[0];
return 0;
}
|
20230706
中途进行了植物学实习，所以没有写代码。当天打了一场 CF 的 div2
CF1847
A.The Man who became a God
简单题，询问你 n 个元素分成 k 个区间（区间内元素编号必须连续），定义一个函数为 f(l,r)=i=l∑r−1∣ai−ai+1∣ 特别地 l=r,f=0
这个时候直接一个 dp 设 f(x,y) 表示前 x 个元素中分成 y 个区间最小值，然后大力转移即可
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=550;
int f[maxn][maxn],a[maxn];
int n,T,m;
int s[maxn];
int g(int x,int y)
{
return s[y-1]-s[x-1];
}
int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=abs(a[i]-a[i+1])+s[i-1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=0x3f3f3f3f;
for(int i=1;i<=n;i++)
f[i][1]=s[i-1];
for(int i=1;i<=n;i++)
for(int k=2;k<=m;k++)
for(int j=1;j<i;j++)
{
f[i][k]=min(f[i][k],f[j][k-1]+g(j+1,i));
}
cout<<f[n][m]<<'\n';
}
}
|
后记：其实直接取前 k−1 个ai−ai+1 就行了，写代码的时候傻逼了。
B. Hamon Odyssey
题目大意，定义一个函数f(l,r)=al&al+1&al+2&…&ar
然后给你一段序列，你需要把这个序列分最多的区间（不分也可以）,并且使得它们的和做小。
显然f(x,y)≤f(x,y+1) 也就是说 f(1,n) 肯定是最大的。
如果它是 0 我们才考虑继续分。
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=200200;
int a[maxn];
int n,T,m;
int s[maxn];
int g(int x,int y)
{
return s[y-1]-s[x-1];
}
int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n;
int sz=0,tmp=0;
for(int i=1;i<=n;i++) cin>>a[i];
tmp=a[1];
for(int i=1;i<=n;i++) tmp&=a[i];
int bas=a[1];
if(tmp!=0)
{
cout<<1<<'\n';
continue;
}
for(int i=1;i<=n;i++)
{
if(bas==-1) bas=a[i];
bas&=a[i];
if(bas==tmp) sz++,bas=-1;
}
cout<<sz<<'\n';
}
}
|
C. Vampiric Powers, anyone?
给你一段序列，假设长度为 m 你可以进行以下操作:
任选一个 i ，然后让 am+1=ai⊕ai+1⊕…⊕am,
此操作无限次使用。
首先我们考虑这个的实际意义。就是把一个序列对称了一下，比如原来的字符串是这样的：
abcde
显然我们引入操作，假设i=3 原来的数组可以变成
abcde(cde)
这时候我们再取i=2
abcde(cde)(cde)edcb
我们可以得到
b,bc,bcd,bcde我们可以任意这样操作，可以得到任意一个区间，原问题就转化成了找到一个区间使得区间异或和最大
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>
using namespace std;
const int maxn=200200;
bool l[maxn][280];
int a[maxn];
int n,T;
int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n;
map <int,int> m1,m2;
for(int i=1;i<=n;i++) cin>>a[i];
int tmp=0;
l[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=255;j++)
{
l[i][j]=0;
}
for(int i=1;i<=n;i++)
{
l[i][a[i]]=1;
for(int j=0;j<=255;j++)
{
l[i][j]=max(l[i-1][j^a[i]],l[i][j]);
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=255;j++)
{
if(l[i][j]) ans=max(ans,j);
}
cout<<ans<<endl;
}
}
|
20230707
Codeforces Round 883 (Div. 3)
c 和 e2 被 hack 了，大寄.
由于 A,B 太水了，不写这俩题
C. Rudolf and the Another Competition
n 个人参加acm赛制，第 i 人解决第 j 题花 ai,j 时间，罚时规定为每个问题被解决的时间之和，最后问你第 1 个人的排名。
很显然直接排序贪心从最简单的问题开始做，但是注意有并列的情况需要考虑（我这边直接又按编号排序，相当于第一个人就是并列的名次）
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200200;
int T,n,m,h;
int ans=0;
int a[maxn];
struct mmm{
int psolv,tm,bh;
bool operator < (const mmm &b)
{
if(psolv==b.psolv)
{
if(tm==b.tm) return bh<b.bh;
return tm<b.tm;
}
return psolv>b.psolv;
}
}q[maxn];
signed main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n>>m>>h;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[j];
}
sort(a+1,a+m+1);
int bast=0,sol=0;
int tm=0;
for(int j=1;j<=m;j++)
{
bast+=a[j];
if(bast>h)
{
break;
}
tm+=bast;
sol++;
}
q[i].bh=i;
q[i].psolv=sol;
q[i].tm=tm;
}
sort(q+1,q+n+1);
for(int i=1;i<=n;i++)
{
if(q[i].bh==1)
{
cout<<i<<'\n';
break;
}
}
}
}
|
D. Rudolph and Christmas Tree
计算面积题，如果两个三角形有交叉一定可以看成一个梯形和三角形，没什么说的。
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=200200;
int n,T;
int d,h;
int a[maxn];
double s;
double checks(int x)
{
double s=0;
if(x==n)
{
s=d;
s=s/2.0*h;
}
else
{
int deltah=a[x+1]-a[x];
if(deltah>=h)
{
s=d;
s=s/2.0*h;
}
else
{
double sd=d-d*(1.0*deltah/h);
sd=sd/2+d*1.0/2;
sd=sd*deltah;
s=sd;
}
}
return s;
}
int main()
{
cin>>T;
while(T--)
{
s=0;
cin>>n>>d>>h;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s+=checks(i);
cout<<setiosflags(ios::fixed)<<setprecision(7)<<s<<endl;
}
}
|
E. Rudolf and Snowflakes
询问 n 是不是一个 k叉树分叉两次以上的顶点个数
换句话说，k进制下表示，一定是 111 这种情况。
对于 111 相当于解一元二次方程
对于 1111 可以提前枚举放进一个map，也可以二分，但是二分有点血流成河别忘了特判
对于 11111 以上的，暴力即可。
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200200;
int n,T;
int d,h;
int a[maxn];
double s;
int check(int x)
{
int tmp=n;
while(tmp%x==1) tmp/=x;
if(!tmp) return 1;
else return 0;
}
signed main()
{
cin>>T;
map <int,int> mp;
for(int i=2;i<=1e6;i++) mp[i*i*i+i*i+i+1]=1;
for(int i=2;i*i*i*i+i*i*i+i*i+i+1<=1e18;i++) mp[i*i*i*i+i*i*i+i*i+i+1]=1;
while(T--)
{
cin>>n;
int bj=0;
for(int i=2;i*i*i*i*i+i*i*i*i+i*i*i+i*i+i+1<=n;i++)
{
if(check(i)) bj=1;
if(bj) break;
}
if(n>=7&&!bj)
{
unsigned int delta=1+4*(n-1);
unsigned int tmp=sqrtl(delta);
if(tmp*tmp!=delta) bj=0;
else if(tmp%2==1ull) bj=1;
}
if(n>=7&&!bj)
{
if(mp[n]) bj=1;
}
if(!bj) cout<<"NO\n";
else cout<<"YES\n";
}
}
|
G. Rudolf and CodeVid-23
简单板子题，用 dij 思想即可。
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2050;
int n,m,T;
int f[maxn];
int bas;
int sol[maxn],bd[maxn],vis[maxn];
int d[maxn];
int check(int x)
{
int tmp=n;
while(tmp%x==1) tmp/=x;
if(!tmp) return 1;
else return 0;
}
int getr()
{
int ans=0;
char t;
for(int i=1;i<=n;i++)
{
ans<<=1;
cin>>t;
ans+=t-'0';
}
return ans;
}
signed main()
{
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=0;i<(1<<n);i++) f[i]=0x3f3f3f3f,vis[i]=0;
bas=getr();
f[bas]=0;
for(int i=1;i<=m;i++)
{
cin>>d[i];
sol[i]=getr();
bd[i]=getr();
}
priority_queue<pair<int,int>> q;
q.push(make_pair(-f[bas],bas));
while(!q.empty())
{
int t=q.top().second;
q.pop();
if(vis[t]) continue;
vis[t]=1;
for(int i=1;i<=m;i++)
{
int s=t-(t&sol[i]);
int b=s|bd[i];
if(f[b]>f[t]+d[i])
{
f[b]=f[t]+d[i];
q.push(make_pair(-f[b],b));
}
}
}
if(f[0]==0x3f3f3f3f) cout<<"-1\n";
else cout<<f[0]<<'\n';
}
}
|
