盒子

【cf#279】A-E

就是要开小号,就是没有做F,就是这么任性。
丢个链接在此。

A:
题意:三个人组队,每个人擅长方向不同。求最多组队种类,并输出组队方式(任意一种)。
用三个vector随便搞搞就能过,种类数是三个vector的最小值。

1Y.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
vector<int> a,b,c;
int main(){
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&m);
if(m==1)a.push_back(i);
else if(m==2)b.push_back(i);
else c.push_back(i);
}
int k=min(a.size(),min(b.size(),c.size()));
cout<<k<<endl;
for(int i=0;i<k;i++)
cout<<a[i]<<" "<<b[i]<<" "<<c[i]<<endl;
return 0;
}

B:
题意:n个人排队,每个人记录自己前面一个人的序号和后面一个人的序号。若没有人就记0,给定n对数字,输出n个数字的序列。
用两个数组c1[i]表示i前面那个人的序号,c2[i]表示i后面那个人的序号。
n若为偶数,从c2[0]向前递推找到第一个人,n若为奇数,找到输入中只出现过一次并且c1[i]!=0是第一个人。
1Y.

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
#include<cstdio>
#include<iostream>
using namespace std;
const int mx = 1e6+5;
int c1[mx],c2[mx],c3[mx];
int main() {
int n,a,b;
int bg = 0,p=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&a,&b);
c1[a]=b,c2[b]=a;
c3[a]++,c3[b]++;
}
if(n%2) {
for(int i=0; i<mx; i++)
if(c3[i]==1) {
if(c1[i]!=0)
bg=i;
}
for(int i=0; i<n/2; i++) {
printf("%d %d ",bg,c1[p]);
bg=c1[bg],p=c1[p];
}
printf("%d",bg);
}
else {
int ed=0;
while(c2[ed]!=0)ed=c2[ed];
for(int i=0;i<n/2;i++){
printf("%d %d ",ed,c1[p]);
p=c1[p],ed=c1[ed];
}
}
return 0;
}

C:
题意:给定一个特别长的数字(长度为1e6)和两个数ab,问是否能将第一个数字拆分成两部分,使得第一部分为第一个数字的倍数而第二部分为第二个数字的倍数。

其实就是MOD+枚举。首先扫一遍处理出是第一个数字倍数的前序。然后从后往前判断是不是第二个数字的倍数就行。
做题的时候没有想出来高位数字怎么加上,看题解上写的是对10的n次方先mod一遍,然后再去乘上高位的数字就行了。

看题解后还WA了两发,好叭一次是忘记注释掉freopen,另一次是逗比写了jud[0]=jud[n-1]=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
42
43
44
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int mx = 1e6+5;
char chr[mx];
bool jud[mx];
int pos[mx];
int main() {
int a,b,p=0,k=0,n;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
memset(jud,0,sizeof(jud));
scanf("%s%d%d",chr,&a,&b);
n=strlen(chr);
for(int i=0; i<n; i++) {
k = k*10 + chr[i] - '0';
k = k % a;
if(k==0)jud[i]=1;
}//枚举前半部分是a的倍数的位置。
pos[0]=1;
for(int i=1; i<n; i++)
pos[i]=(pos[i-1]*10)%b;
k=0;//处理指数
for(int i=n-1; i>=0; i--) {
k = (k+pos[n-i-1]*(chr[i]-'0'))%b;
if(jud[i-1]&&(k==0)&&(chr[i]-'0')) {
p=i;
break;
}
}//从后往前判断后面是b的倍数的位置。
if(p==0) {
cout<<"NO"<<endl;
}
else {
cout<<"YES"<<endl;
for(int i=0;i<p;i++)
printf("%c",chr[i]);
cout<<endl;
for(int i=p;i<n;i++)
printf("%c",chr[i]);
}
return 0;
}

D:
题目:给两个大小分别是a1a2和b1b2的巧克力,问你是否能通过操作将它们变成一样大的巧克力。操作有:将边变成原来的1/2或者是2/3,但是必须保证转换后边仍然为整数。

分别记录两个能够除2和3的最大数量,【记得先处理3,因为除以3的时候需要在2的统计那里+1。//不太好表示啊SAD,看代码叭。
然后判断缩到最小的时候二者是不是一样大,如果不是直接输出-1。是则各种处理一下输出就好。

依旧参考题解+忘记注释,结果TLE在了test1上一发。

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
#include<cstdio>
#include<iostream>
using namespace std;
int main() {
long long a1,a2,b1,b2,s1,s2;
int p0,p1,q0,q1,res;
p0=p1=q0=q1=res=0;
scanf("%I64d%I64d%I64d%I64d",&a1,&a2,&b1,&b2);
s1=a1*a2;
s2=b1*b2;
//cout<<s1<<" "<<s2<<endl;
while(s1%2==0) {
p0++;
s1/=2;
}
while(s1%3==0) {
p1++;
s1/=3;
}
while(s2%2==0){
q0++;
s2/=2;
}
while(s2%3==0){
q1++;
s2/=3;
}
//cout<<p0<<" "<<p1<<" "<<q0<<" "<<q1<<endl;
if(s1!=s2){
cout<<"-1"<<endl;
return 0;
}
if(p1>q1){
while(p1>q1){
if(a1%3==0){
a1/=3;a1*=2;
}
else{
a2/=3;a2*=2;
}
p1--;res++;p0++;
}
}
else{
while(p1<q1){
if(b1%3==0){
b1/=3;b1*=2;
}
else{
b2/=3;b2*=2;
}
q1--;res++;q0++;
}
}
if(p0>q0){
while(p0>q0){
if(a1%2==0){
a1/=2;
}
else{
a2/=2;
}
p0--;res++;
}
}
else{
while(p0<q0){
if(b1%2==0){
b1/=2;
}
else{
b2/=2;
}
q0--;res++;
}
}
cout<<res<<endl;
cout<<a1<<" "<<a2<<endl;
cout<<b1<<" "<<b2<<endl;

return 0;
}

E:
题意:
给你n个数字,一些数位被问号取代,问你有没有可能将其处理成升序数列。

对每个数字将其处理成比上面一个数字大的最小可能数字就可以。

敲完了AB就开始打这道题,结果这道题敲了一天也是醉了,各种分类讨论最终还是花样WA。看别人代码写的好简单啊SAD。
WA了11发。哭。

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<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int mx = 1e5+5;
char chr[mx][10];
int num[mx];
int get(char *s) {
int res=0;
for(int i=0; i<strlen(s); i++)
res =res * 10 + (s[i] == '?' ? 9 : s[i]-'0');
return res;
}
//对每一位进行赋值都赋它的最小可能值就好。
int fn(int pos) {
int k=0,q=num[pos-1];
int n=strlen(chr[pos]);
for(int i=0; i<n; i++) {
if(chr[pos][i]=='?') {
char low = i==0 ? '1' : '0';
for(int j=low; j<='9'; j++) {
chr[pos][i]=j;
int now = get(chr[pos]);
if(now>q) {
break;
}
}
}
}
for(int i=0;i<n;i++)
k=k*10+chr[pos][i]-'0';
return k;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int n,l,k=0;
bool flag=true;
scanf("%d",&n);
for(int i=0; i<n; i++)
scanf("%s",chr[i]);
l=strlen(chr[0]);
if(chr[0][0]=='?')chr[0][0]='1';
k=chr[0][0]-'0';
for(int i=1; i<l; i++) {
if(chr[0][i]=='?')chr[0][i]='0';
k=k*10+chr[0][i]-'0';
}
num[0]=k;
for(int i=1; i<n; i++) {
num[i]=fn(i);
}
for(int i=1; i<n; i++) {
if(num[i-1]>=num[i]) {
flag=false;
break;
}
}
if(flag) {
puts("YES");
for(int i=0; i<n; i++)
printf("%d\n",num[i]);
}
else puts("NO");
return 0;
}

附错误的代码,因为没找到反例TAT。【个人感觉还挺对←.←。。。果然应该遵守KISS原则啊。

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
#include<cstdio>
#include<iostream>
#include<cstring>
int pow[]= {1,10,100,1000,10000,100000,1000000,10000000,100000000};
using namespace std;
const int mx = 1e5+5;
char chr[mx][10];
int num[mx];
int fn(int pos) {
int k=0,sta;
bool jud=false;
int q=num[pos-1];
int cc;
int n=strlen(chr[pos]);//如果当前数字的长度比上一个数字的长度长,就将所有的问号赋值为0(第一位如果是问号的话就赋值为1
if(n>strlen(chr[pos-1])) {
if(chr[pos][0]=='?')chr[pos][0]='1';
k=chr[pos][0]-'0';
for(int i=1; i<n; i++) {
if(chr[pos][i]=='?')chr[pos][i]='0';
k=k*10+chr[pos][i]-'0';
}
return k;
}
//此时两个数字的位数相等。
bool flag = false;
for(int i=0; i<n; i++) {
int be = q / pow[n-i];
//be表示前一个数字的前缀,如果到某一个数字时,be比现在要小,那么就可以给所有的数字都赋值为0,否则用上一个数字的该位置的数给他赋值
if(be<k) {
if(chr[pos][i]=='?')chr[pos][i]='0';
k=k*10+chr[pos][i]-'0';
}
else {
if(chr[pos][i]=='?')
k=k*10+chr[pos-1][i]-'0';
else
k=k*10+chr[pos][i]-'0';
}
}
//如果这样赋值的话得到的答案比上一个数字大,那么直接返回。
if(k>q) {
int kk=k;
for(int i=n-1;i>=0;i--){
chr[pos][i]=kk%10+'0';
kk=kk/10;
}
return k;
}
//否则从小到大找问号,如果问号的位置在上一个数字里面为9那么接着往前找,找到第一个不为9的位置state。
//state前面的那些数和前一个数字保持相等,state的数字是前一个数字在该位置的数字+1,state后面的问号全都赋值为0。
int kk=0;
bool fuc = true;
sta=n;
for(int i=n-1; i>=0; i--) {
if(chr[pos][i]=='?') {
if(chr[pos-1][i]=='9')
sta=i;
else
break;
}
}
for(int i=n-1; i>=sta; i--) {
if(chr[pos][i]=='?')chr[pos][i]='0';
}
for(int i=sta-1; i>=0; i--) {
if(chr[pos][i]=='?') {
chr[pos][i]=chr[pos-1][i]+1;
break;
}
}
for(int i=0; i<n; i++) {
if(chr[pos][i]=='?')chr[pos][i]=chr[pos-1][i];
}
for(int i=0; i<n; i++) {
kk=kk*10+chr[pos][i]-'0';
}
return kk;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
memset(num,0,sizeof(num));
int n,l,k=0;
bool flag=true;
scanf("%d",&n);
for(int i=0; i<n; i++)
scanf("%s",chr[i]);
l=strlen(chr[0]);
if(chr[0][0]=='?')chr[0][0]='1';
k=chr[0][0]-'0';
for(int i=1; i<l; i++) {
if(chr[0][i]=='?')chr[0][i]='0';
k=k*10+chr[0][i]-'0';
}
num[0]=k;
k=0;
for(int i=1; i<n; i++) {
num[i]=fn(i);
}
for(int i=1; i<n; i++) {
if(num[i-1]>=num[i]) {
flag=false;
break;
}
}
// flag=true;
if(flag) {
puts("YES");
for(int i=0; i<n; i++)
printf("%d\n",num[i]);
}
else puts("NO");
return 0;
}