Codeforces Round #539 (Div. 2)
1 #include<bits/stdc++.h>
2 #include<iostream>
3 #include<cstdio>
4 #include<cstdlib>
5 #include<cstring>
6 #include<cmath>
7 #include<algorithm>
8 #include<queue>
9 #include<vector>
10 #include<map>
11 #define lson i<<1
12 #define rson i<<1|1
13 #define LS l,mid,lson
14 #define RS mid+1,r,rson
15 #define mem(a,x) memset(a,x,sizeof(a))
16 #define gcd(a,b) __gcd(a,b)
17 #define ll long long
18 #define ull unsigned long long
19 #define lowbit(x) (x&-x)
20 #define pb(x) push_back(x)
21 #define enld endl
22 #define mian main
23 #define itn int
24 #define prinft printf
25 #pragma GCC optimize(2)
26 //#pragma comment(linker, "/STACK:102400000,102400000")
27
28 const double PI = acos (-1.0);
29 const int INF = 0x3f3f3f3f;
30 const int EXP = 1e-8;
31 const int N = 1e5 + 5;
32 const int MOD = 1e9 + 7;
33 const int MAXN = 1e5 + 5;
34
35 using namespace std;
36
37 int n,v;
38 int main() {
39 cin>>n>>v;
40 if(n-1<=v) {
41 cout<<n-1<<endl;
42 return 0;
43 }
44 int ans=v;
45 for(int i=2;i<=n-1-v+1;++i) ans+=i;
46 cout<<ans<<endl;
47 }
A - Sasha and His Trip
B - Sasha and Magnetic Machines
1 #include<bits/stdc++.h>
2 #include<iostream>
3 #include<cstdio>
4 #include<cstdlib>
5 #include<cstring>
6 #include<cmath>
7 #include<algorithm>
8 #include<queue>
9 #include<vector>
10 #include<map>
11 #define lson i<<1
12 #define rson i<<1|1
13 #define LS l,mid,lson
14 #define RS mid+1,r,rson
15 #define mem(a,x) memset(a,x,sizeof(a))
16 #define gcd(a,b) __gcd(a,b)
17 #define ll long long
18 #define ull unsigned long long
19 #define lowbit(x) (x&-x)
20 #define pb(x) push_back(x)
21 #define enld endl
22 #define mian main
23 #define itn int
24 #define prinft printf
25 #pragma GCC optimize(2)
26 //#pragma comment(linker, "/STACK:102400000,102400000")
27
28 const double PI = acos (-1.0);
29 const int INF = 0x3f3f3f3f;
30 const int EXP = 1e-8;
31 const int N = 1e5 + 5;
32 const int MOD = 1e9 + 7;
33 const int MAXN = 1e5 + 5;
34
35 using namespace std;
36
37 int vis[105],n,sum,tmp,Min;
38 vector<int> p;
39
40 void init() {
41 mem(vis,0),sum=0,Min=INF;
42 }
43
44 void Solve(int n) {
45 p.clear();
46 for(int i=2; i<=n; i++) {
47 if(n%i==0) {
48 p.push_back(i);
49 }
50 }
51 }
52
53 int main() {
54 init();
55 scanf("%d",&n);
56 for(int i=1; i<=n; ++i) {
57 scanf("%d",&tmp);
58 sum+=tmp;
59 vis[tmp]=1;
60 Min=min(Min,tmp);
61 }
62 int ans=sum;
63 for(int i=Min+1; i<=100; ++i)
64 if(vis[i]) {
65 Solve(i);
66 if(p.size()==1) continue;
67 for(int j=0; j<p.size(); ++j) {
68 ans=min(ans,sum-(i-i/p[j])+Min*p[j]-Min);
69 // cout<<j<<' '<<p[j]<<endl;
70 }
71 }
72 cout<<ans<<endl;
73 }
B - Sasha and Magnetic Machines
1、交换律
2、结合律（即(a^b)^c == a^(b^c)）
3、对于任何数x，都有x^x=0，x^0=x
4、自反性 A XOR B XOR B = A xor 0 = A
前缀异或