最近一直很忙没什么时间去写题目，也就是抽空来看了几道题，周二下午没课来集中写了写。
A 题
很简单，学过高中知识就会写。
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
cout<<(a+(a - b))<<endl;
return 0;
}
|
B 题
和上道题差不多，唯一不同的就是加了一个字符串处理（将string 变成
int）。
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
| #include<bits/stdc++.h>
using namespace std;
string s;
long long num(long long l,long long r){
long long base = 1,ans = 0;
for(long long i=r;i>=l;i--){
ans += (s[i] - '0')*base;
base = base * 10;
}
return ans;
}
int main()
{
cin>>s;
long long n = s.length();
long long start = 0,end = 0;
for(long long i=0;i<n;i++){
if(s[i] == ','){
end = i-1;
break;
}
}
long long a = num(start,end);
start = end+2;
for(long long i=end+2;i<n;i++){
if(s[i] == ','){
end = i-1;
break;
}
}
long long b = num(start,end),c = num(end+6,n-1);
long long d = (b - a);
cout<<(c - b) / d - 1<<endl;
return 0;
}
|
C 题
就是数学加物理题，根据镜面反射的原理，很显然我们需要将 \(z\)
轴的坐标镜面对称。最后同时除以他们的最大公约数就行了。
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
| #include<bits/stdc++.h>
using namespace std;
long long n,k;
long long gcd(long long a,long long b){return b == 0 ? a : gcd(b,a%b);}
int main()
{
cin>>n>>k;
for(long long i=1;i<=n;i++){
long long x,y,z;
cin>>x>>y>>z;
z = 2*k - z;
long long t = gcd(gcd(x,y),z);
if(x % t == 0) x = x / t;
if(y % t == 0) y = y / t;
if(z % t == 0) z = z / t;
cout<<x<<" "<<y<<" "<<z<<endl;
}
return 0;
}
|
D 题
稍微有点难，但是稍微想想也能出来。
看了数据范围为全都 \(\leq
7\)，每个计划只有取和不取两种选择，那么我们最多的方案有 \(2^7 =
128\)，所以很简单枚举每一种就行了，但是怎么让方案数与每一种的方案关联处理呢？
联系到快速幂，我们可以想到与二进制结合起来。这样就很简单就可以算出来了，剩下的就是循环和判断的事了，对了，题目默认方案之间可以有重叠（错过一次）。
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn = 10;
const int maxq = 7;
int t[maxn][maxn],a[maxn][maxn][maxn];
int main()
{
int n,m,q;
cin>>n>>m>>q;
for(int i=0;i<n;i++){
string s;
cin>>s;
for(int j=0;j<m;j++)
t[i][j] = (s[j] - '0');
}
for(int i=0;i<q;i++){
for(int j=0;j<n;j++){
string s;
cin>>s;
for(int k=0;k<m;k++)
a[i][j][k] = (s[k] - '0');
}
}
int anscnt = pow(2,q),ans = -1;
for(int i=0;i<pow(2,q);i++){
bitset<maxq> bits(i);
int scheme[maxn][maxn],cnt = bits.count();
memset(scheme,0,sizeof(scheme));
for(int j=0;j<q;j++){
if(bits[j] == 1){
for(int x=0;x<n;x++)
for(int y=0;y<m;y++)
scheme[x][y] += a[j][x][y];
}
}
bool flag = 1;
for(int x=0;x<n;x++)
for(int y=0;y<m;y++){
if(t[x][y] == 1 && scheme[x][y] == 0) continue;
else if(t[x][y] == 0 && scheme[x][y] >= 1) continue;
else flag = 0;
}
if(flag == 1)
if(anscnt > cnt) anscnt = cnt,ans = i;
}
if(ans == -1) cout<<ans<<endl;
else{
cout<<anscnt<<endl;
bitset<maxq> bits(ans);
for(int i=0;i<q;i++)
if(bits[i] == 1)
cout<<i+1<<" ";
}
return 0;
}
|
E 题
说实话，到现在我还没有写出来，感觉是常数太大的问题，感觉时间复杂度没啥太大的问题。感觉极限能过。（突然想到会退化了）
我的想法是，先用前缀和算出前 \(n\)
项和，顺便再记录正数的数字位置，将每个放入 map
中。然后再枚举后面的一个划分点，然后在用 lower_bound()
记录算出区间里有没有正数，就 OK 了。
但是我这个想法会退化，如果数据的许多小区间中，前缀和有相同的，就比如
1 -1 1 -1 1 -1 1 -1， 会退化成 \(O(n)\) 查找每个区间。
所以最坏时间复杂度应该为 \(\Theta (n^2 \log
n)\)
平均时间复杂度为 \(O (n \log n \log
n)\)
我在夜里突然想到一个很简单的结论，就是划分的三个数组一定是 \(\frac{S}{3}\)，那么只需要加上这个判断，那么时间复杂度就会大大下降。wok，这个第一次看我还真没想到这么显然的结论。
那么优化过的最坏时间复杂度下降到 \(\Theta
(n \log n)\)。
平均时间复杂度为 \(O (n + \log
n)\)
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>
using namespace std;
const int maxn = 200010;
int a[maxn],sum[maxn];
map<int,vector<int> > m;
vector<int> pos;
int main()
{
int n;
cin>>n;
int cnt = 0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i] > 0) pos.push_back(i);
cnt += a[i];
}
if(cnt % 3 != 0 || pos.size() < 3){cout<<0<<endl;return 0;}
sum[1] = a[1];
for(int i=2;i<=n;i++)
sum[i] = sum[i-1] + a[i];
for(int i=1;i<n-1;i++)
if(sum[i] == cnt / 3)
m[sum[i]].push_back(i);
int ans = 0;
for(int i=n;i>1;i--){
int num = sum[n] - sum[i-1];
if(m.count(num) == 1 && num == cnt / 3){
for(int it : m[num]){
if(i <= it) continue;
int num2 = sum[i-1] - sum[it];
auto a1 = lower_bound(pos.begin(),pos.end(),1);
auto a2 = lower_bound(pos.begin(),pos.end(),it+1);
auto a3 = lower_bound(pos.begin(),pos.end(),i);
if(num2 == num && a1 != pos.end() && a2 != pos.end() && a3 != pos.end()){
if(*a1 <= it && *a2 <= i-1 && *a3 <= n) ans ++;
}
}
}
}
cout<<ans<<endl;
return 0;
}
|