2024CCPC重庆vp
题目链接：2024CCPC重庆
J
签到
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
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<int>
#define vecp vector<pair<int,int>>
const int N=1e6+5;
const int MOD=998244353;
const int INF=1e18;
int n,m;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
inline void Add(int& x,int y){
x+=y;
if(x>=MOD)x%=MOD;
}
int Mul(int x,int y){
x*=y;
if(x>=MOD)x%=MOD;
return x;
}
void init(){
}
void solve(){
cin>>n>>m;
cout<<6*n*m<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
|
B
按公式写就行，需要注意这题的精度有点小问题，应该用float。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<int>
#define vecp vector<pair<int,int>>
const int N=1e6+5;
const int MOD=998244353;
const int INF=1e18;
int n;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
inline void Add(int& x,int y){
x+=y;
if(x>=MOD)x%=MOD;
}
int Mul(int x,int y){
x*=y;
if(x>=MOD)x%=MOD;
return x;
}
void init(){
}
void solve(){
int ppmax, a,b,c,d,e,f;
cin >> ppmax >> a >> b >> c >> d >> e >> f;
float acc = 1.0*(300*a+300*b+200*c+100*d+50*e)/(300*(a+b+c+d+e+f));
float pp = max(0.0, 1.0*(320*a+300*b+200*c+100*d+50*e+0)/(320*(a+b+c+d+e+f))-0.8)*5*ppmax;
float ans_acc = 100*acc;
cout << fixed << setprecision(2) << ans_acc << "% ";
cout << fixed << setprecision(0) << pp << "\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
K
先确定$A_1$的图形，发现对于$A_n$，都是由$A_{n-1}$填充了上下左右中五个区域，四个角填充0构成的。
因此确定想要答案为1，需要三进制的数每一位都有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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<int>
#define vecp vector<pair<int,int>>
const int N=1e6+5;
const int MOD=998244353;
const int INF=1e18;
int n;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
inline void Add(int& x,int y){
x+=y;
if(x>=MOD)x%=MOD;
}
int Mul(int x,int y){
x*=y;
if(x>=MOD)x%=MOD;
return x;
}
void init(){
}
void solve(){
cin>>n;
string s1,s2;
cin>>s1>>s2;
s1=' '+s1;
s2=' '+s2;
fr(i,n){
if(s1[i]!='1' &&s2[i]!='1'){
cout<<0<<endl;
return;
}
}
cout<<1<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--){
solve();
}
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<int>
#define vecp vector<pair<int,int>>
const int N=1e5+5;
const int MOD=998244353;
const int INF=1e18;
int n,m;
vec e[N];
pair<int,int>a[N];
int vis[N];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
inline void Add(int& x,int y){
x+=y;
if(x>=MOD)x%=MOD;
}
int Mul(int x,int y){
x*=y;
if(x>=MOD)x%=MOD;
return x;
}
void init(){
}
void solve(){
cin>>n>>m;
int u,v;
int mx1,mx2;
vec son(n+1,0);
fr(i,n){
cin>>a[i].first;
a[i].second=i;
}
sort(a+1,a+1+n,greater<pair<int,int>>());
mx1=a[1].second,mx2=a[2].second;
fr(i,m){
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
son[u]++;
son[v]++;
}
if(n==1){
cout<<a[1].first<<endl;
return;
}
if(son[mx1]<2){
cout<<a[2].first<<endl;
}
else cout<<a[1].first<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
|
I
显然我们的问题是如何去处理1。
如果将1加到别的数上，那么对于结果的影响就是$(n+1)/n$，如果将n个1相加，对于结果的影响是$\sqrt[n]{n}$。
比较后发现，最优解是先将1加到2上，此时对结果的影响是1.5倍。其次是三个1合成3，对结果的影响是1.442，然后是2个1合成2，对结果的影响是1.414，因此得到处理方法：先将1全加到2上， 然后对剩下的1合成3，如果最后剩下2个1，合成2，剩下一个则加到3上。
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<int>
#define vecp vector<pair<int,int>>
const int N=1e6+5;
const int MOD=998244353;
const int INF=1e18;
int n;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
inline void Add(int& x,int y){
x+=y;
if(x>=MOD)x%=MOD;
}
int Mul(int x,int y){
x*=y;
if(x>=MOD)x%=MOD;
return x;
}
void init(){
}
void solve(){
int a[11];
memset(a,0,sizeof(a));
for(int i=1;i<=9;i++)
cin>>a[i];
if(a[1]<=a[2]) {
a[3]+=a[1];
a[2]-=a[1];
a[1]=0;
goto ok;
}
else
{
a[3]+=a[2];
a[1]-=a[2];
a[2]=0;
if(a[1]==1) {
for(int i=2;i<=9;i++)
{
if(a[i]!=0)
{
a[i+1]++;
a[i]--;
a[1]=0;
goto ok1;
}
}
ok1:goto ok;
}
if(a[1]%3==0) {
a[3]+=a[1]/3;
a[1]=0;
goto ok;
}
if(a[1]%3==1) {
a[3]+=a[1]/3;
a[3]--;
a[4]++;
a[1]=0;
goto ok;
}
if(a[1]%3==2) {
a[3]+=a[1]/3;
a[2]++;
a[1]=0;
goto ok;
}
}
ok:;
int ans=1;
for(int i=1;i<=10;i++)
{
ans=ans*ksm(i,a[i])%MOD;
}
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
C
首先将特殊情况，即全是 . 或全是#的情况分类讨论掉。
我们现在考虑的即为如何将所有矩形相联的同时避免矩形1的冲突。
其实很简单：只需要每一行都是独立的矩阵，不与相邻行组成矩阵即可。
对于第2行和第6行，是第1行和第7行的镜像翻转，然后对于第3行和第5行，只放一个#，第四行将这两个#相联即可。
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<int>
#define vecp vector<pair<int,int>>
const int N=1e6+5;
const int MOD=998244353;
const int INF=1e18;
int n;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
inline void Add(int& x,int y){
x+=y;
if(x>=MOD)x%=MOD;
}
int Mul(int x,int y){
x*=y;
if(x>=MOD)x%=MOD;
return x;
}
void init(){
}
void solve(){
cin>>n;
string s,t;
cin>>s>>t;
int cnt1=0,cnt2=0;
for(auto i:s){
if(i=='#')cnt1++;
}
for(auto i:t){
if(i=='#')cnt2++;
}
if(cnt1==n){
if(cnt2==n||cnt2==0){
cout<<"YES"<<endl;
cout<<s<<endl;
fr(i,5){
fr(j,n)cout<<'#';
cout<<endl;
}
cout<<t<<endl;
}
else {
cout<<"NO"<<endl;
}
return;
}
if(cnt2==n){
if(cnt1==n||cnt1==0){
cout<<"YES"<<endl;
cout<<s<<endl;
fr(i,5){
fr(j,n)cout<<'#';
cout<<endl;
}
cout<<t<<endl;
}
else {
cout<<"NO"<<endl;
}
return;
}
if(cnt1==0&&cnt2==0){
cout<<"YES"<<endl;
cout<<s<<endl;
fr(i,5){
fr(j,n)cout<<'#';
cout<<endl;
}
cout<<t<<endl;
return;
}
vector<string>ans(10);
ans[1]=s;
ans[7]=t;
for(auto i:ans[1]){
if(i=='#')ans[2]+='.';
else ans[2]+='#';
}
for(auto i:ans[7]){
if(i=='#')ans[6]+='.';
else ans[6]+='#';
}
int fir=0;
int pos1=0,pos2=0;
for(int i=0;i<n-1;i++){
if(ans[2][i]=='.'&&ans[2][i+1]=='#'&&fir==0){
pos1=i;
fir=1;
}
else if(ans[2][i]=='#'&&ans[2][i+1]=='.'&&fir==0){
pos1=i+1;
fir=1;
}
}
for(int i=0;i<n;i++){
if(i==pos1){
ans[3]+='#';
}
else ans[3]+='.';
}
fir=0;
for(int i=0;i<n-1;i++){
if(ans[6][i]=='.'&&ans[6][i+1]=='#'&&fir==0){
pos2=i;
fir=1;
}
else if(ans[6][i]=='#'&&ans[6][i+1]=='.'&&fir==0){
pos2=i+1;
fir=1;
}
}
for(int i=0;i<n;i++){
if(i==pos2){
ans[5]+='#';
}
else ans[5]+='.';
}
if(abs(pos1-pos2)<2){
for(auto i:ans[3]){
ans[4]+=i;
}
}
else {
for(int i=0;i<n;i++){
if(i>min(pos1,pos2)&&i<max(pos1,pos2)){
ans[4]+='#';
}
else ans[4]+='.';
}
}
cout<<"YES"<<endl;
fr(i,7){
cout<<ans[i]<<endl;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
D
对于b，有$b=2^{x1}*5^{y1}*p，(gcd(p,10)=1)$。对于d，有$d=2^{x2}*5^{y2}*q，(gcd(q,10)=1)$。
则有
$$
a/b+c/d=(ad+bc)/bd
$$
$$
(ad+bc)/bd=(ad/pq+bc/pq)/2^{x1+x2}5^{y1+y2}
$$
$$
w=ad/pq+bc/pq
$$
$$
wpq=ad+bc
$$
由裴蜀定理，对于ax+by=c有解的条件是$gcd(a,b)|c$得：
设w，c为x，y，有$gcd(pq,-b)=gcd(pq,b)|ad$，则有$gcd(pq,2^{x1}5^{y1}p)=p,ad=a*2^{x2}5^{y2}q,p|aq$。因为ab互质。所以$ p|q$。
同理，设w，a为x，y，有$ q|p$。
则有p=q。
因此目前要做的是对$wp^2=ad+bc$求解，设c，w为未知数，枚举d，然后用exgcd求解。
求解出c以后需要将c缩到最小，因此c每次需要减小$lcm(b,p^2)/b$，直到c下一次减小小于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
| #include<bits/stdc++.h>
using ll=long long;
using namespace std;
ll T,a,b,w,z,d,c,k,ac,ad;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=1,y=0;
return a;
}
ll g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
int main()
{
cin>>T;
while(T--)
{
cin>>a>>b,w=b;
while(w%2==0)w/=2;
while(w%5==0)w/=5;
b/=w,ac=1e9;
for(z=1;z*w<1e9;z*=5)
for(d=z;d*w<1e9;d*=2)
{
ll g=exgcd(w,-b,k,c),o=abs(w/g);
c=(c*a*d/g%o+o)%o;
if(c<ac)ac=c,ad=d*w;
}
cout<<ac<<' '<<ad<<'\n';
}
return 0;
}
|