牛客寒假训练赛1

寒假就来了!(其实十天前就回家了,嘻嘻

本以为寒假会好好学习的,其实也并没有,python断了很久了,做过几题水题,终于打了第一场训练赛,两题挂机
大概这就是所谓的:间歇性踌躇满志,持续性混吃等死,不由得让我想起了king巨…等会下面放张图片…
前天和啊伟秀儿出去完了一天,挺开心的,虽然吃到恶心但是一年没见再次相聚对我来说真的很开心!

放图哈哈哈哈忽略水印,我就是这么不讲究

家里真的冷…

言归正传
比赛链接:https://ac.nowcoder.com/acm/contest/317#question
我就说四题…能力范围问题
A:
水题模拟(反向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#define int long long
using namespace std;
int mode(int x,int a,int b){
if(x==1)return a-b;
if(x==2)return a+b;
if(x==3)return a/b;
if(x==4)return a*b;
else return 0;
}
int apt[1005],num[1005];
signed main(){
int n,x;
cin>>n>>x;
for(int i=0;i<n;i++){
cin>>apt[i]>>num[i];
}
for(int i=n-1;i>=0;i--){
x=mode(apt[i],x,num[i]);
}
cout<<x<<endl;
return 0;
}

B:
往死里if:

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 <bits/stdc++.h>
#define int long long
using namespace std;
int a[100005]={0};
int want[100005];
int zero=0,two=0,four=0;
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
if(a[i]==0)zero++;
if(a[i]==2)two++;
if(a[i]==4)four++;
}
want[0]=0;
for(int i=1;i<=n;i++){
if(want[i-1]==0){
if(four!=0){
four--;
want[i]=4;
continue;
}
else{
if(two!=0){
two--;
want[i]=2;
continue;
}
if(two==0&&zero!=0){
zero--;
want[i]=0;
continue;
}
}
}
else if(want[i-1]==4){
if(zero!=0){
zero--;
want[i]=0;
continue;
}
else{
if(two!=0){
two--;
want[i]=2;
continue;
}
if(two==0&&four!=0){
four--;
want[i]=4;
continue;
}
}
}
else if(want[i-1]==2){
if(zero!=0){
zero--;
want[i]=0;
continue;
}
if(zero==0&&four!=0){
four--;
want[i]=4;
continue;
}
if(zero==0&&four==0&&two!=0){
two--;
want[i]=2;
continue;
}
}
}
int wyh=0;
for(int i=1;i<=n;i++){
wyh+=(want[i]-want[i-1])*(want[i]-want[i-1]);
}
cout<<wyh<<endl;
return 0;
}

C:
这题有想法觉得能做出来但是最后写到一半卡住了就跳了,最后看题解是开二维数组写背包dp,后面再学习学习吧
此处粘一下官方:

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>
#define LL long long
using namespace std;
const int MAXN = 10003, INF = 1e9 + 10;
void chmin(int &a, int b) {a = (a < b ? a : b);}
void chmax(int &a, int b) {a = (a > b ? a : b);}
int sqr(int x) {return x * x;}
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, mx;
bool f[MAXN][MAXN];
struct Node {
int id, val;
bool operator < (const Node &rhs) const {
return val > rhs.val;
}
}a[MAXN];
signed main() {
//freopen("a2.in", "r", stdin);
//cout << (457 ^ 23);
N = read();
for(int i = 1; i <= N; i++) a[i].id = i, a[i].val = read(); mx = 6001;
sort(a + 1, a + N + 1);
for(int i = 1, flag = 1; i <= N; i++) {
if(a[i].id == 1) {flag = 0, f[i][a[i].val] = 1; continue;}
if(flag) continue;
if(a[i].id == N) {
int k = i - 1;
while(k && a[i].val == a[k].val) k--;
if(!k) break;
for(int j = mx; j >= 0; j--) {
f[i][j] |= f[k][j ^ a[i].val];
if(f[i][j]) {printf("%d", j); return 0;}
}
break;
}
else if(a[i].val == a[i - 1].val) {
memcpy(f[i], f[i - 1], sizeof(f[i]));
}
else {
for(int j = 0; j <= mx; j++)
f[i][j] |= (f[i - 1][j ^ a[i].val] | f[i - 1][j]);
}
}
puts("-1");
return 0;
}

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
41
42
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e9+7;
int quick_pow(int x,int y,int mod){
int ans=1,base=x;
while(y!=0){
if(y&1==1){
ans*=base;
ans%=mod;
}
base*=base;
base%=mod;
y>>=1;
}
return ans%mod;
}
int erla(int n){
int res=n;
for(int i=2;i*i<n;i++){
if(n%i==0){
res/=i;
res*=i-1;
while(n%i==0)
n/=i;
}
}
if(n^1){
res/=n;
res*=n-1;
}
return res;
}
signed main(){
int n,k,a,b;
cin>>n>>k>>a>>b;
int cnm=(a+b)%maxn;
int wyh=((n%maxn)*((erla(n)/2)%maxn)%maxn)%maxn;
int ans=cnm*quick_pow(k%maxn,wyh,maxn)%maxn;
cout<<ans<<endl;
return 0;
}

只看了这些题,但是写博客就是为了下次回来看没做的题:俗称插眼

说到king巨,一张图:

中科院尚如此,何况我一个双非,加油啊晚风!

下学期退出了学生会要学会学习了,这学期成绩又崩了呜呜呜呜

晚风。
coswindy

-------------本文结束感谢您的阅读-------------