A

纯手速,本来2min就能A,手残5min才A
A出来的时候已经1600+了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

const int maxn=1010;
typedef long long ll;

int main()
{
//freopen("test.txt","r",stdin);
ll n,w,k,s;
cin>>k>>n>>w;
s=((1+w)*w)/2*k;
s-=n;
cout<<(max(0LL,s))<<endl;
return 0;
}

B

这题终测被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
#include<bits/stdc++.h>
using namespace std;

const int maxn=6010;
typedef long long ll;
int vis[maxn];

int main()
{
// freopen("test.txt","r",stdin);
int n;
memset(vis,0,sizeof vis);
scanf("%d",&n);
for(int i=0;i<n;++i){
int x;
scanf("%d",&x);
++vis[x];
}
int ans=0;
for(int i=0;i<=maxn;++i){
if(vis[i]>1){
ans+=vis[i]-1;
vis[i+1]+=vis[i]-1;
}
}
printf("%d\n",ans);
return 0;
}

C

刚开始按bfs用数位表示状态写的,结果越写越残(有个10坑死人),然后突然意识到只有一种操作,不需要dfs,直接模拟就行了。。。
需要注意的一个地方是无解时候跳出,一般是判重跳出,然而判重并不方便,这里(瞎)取了一个足够大的值,操作次数超过了就跳出

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
#include<bits/stdc++.h>
using namespace std;

queue<int> q[2];
int INF=100001;

int main()
{
// freopen("test.txt","r",stdin);
int n,t,x;
scanf("%d",&n);
for(int i=0;i<2;++i){
scanf("%d",&t);
for(int j=0;j<t;++j){
scanf("%d",&x);
q[i].push(x);
}
}
t=0;
while(t<INF){
if(q[0].empty() || q[1].empty()){
printf("%d %d\n",t,q[0].empty()?2:1);
return 0;
}
int p1=q[0].front(),p2=q[1].front(); q[0].pop(); q[1].pop();
if(p1>p2){
q[0].push(p2);
q[0].push(p1);
}else{
q[1].push(p1);
q[1].push(p2);
}
++t;
}
printf("-1\n");
return 0;
}

D

题目要求操作次数尽量多,因此每次都选质因子。
即给出a,b,求a!/b!的质因子个数
用到了阶乘的质因数分解,这里预处理出前缀和就可以了, 答案为ans[a]-ans[b]

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
#include<bits/stdc++.h>
using namespace std;

#define N 5000000
const int maxn=5000010;
int vis[maxn];
int res[maxn];

void init(){
memset(res,0,sizeof res);
memset(vis,0,sizeof vis);
for(int i=2;i<=N;++i){
if(!vis[i]){
++vis[i];
for(int j=i+i;j<=N;j+=i){
int t=j;
while(t%i==0){
t/=i;
++vis[j];
}
}
}
res[i]+=res[i-1]+vis[i];
}
}

int a,b;

int main()
{
init();
int t;
scanf("%d",&t);
while(t--){
scanf("%d %d",&a,&b);
printf("%d\n",res[a]-res[b]);
}
return 0;
}