20210706-2020ICPC-seoul

字数统计: 1.3k字   |   阅读时长: 7分
训练题解
solved A B C D E F G H I J K L
5 / 12 · O · O O · Ø Ø ! · · ·
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

比赛链接

B - Commemorative Dice

solved by Tryna. 0:09(+)

题解： 签到题

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

typedef long long ll;
const int maxn = 1e5 + 7;
const int N = 1e5 + 7;
int a[10], b[10];
int gcd(int a, int b) {
    return a == 0 ? b : gcd(b %a, a);
}
void run() {
    for(int i = 1; i <= 6; i++) {
        scanf("%d", &a[i]);
    }
    int num = 36;
    int ans = 0;
    for(int i = 1; i <= 6; i++) {
        scanf("%d", &b[i]);
        for(int j = 1; j <= 6; j++) {
            if(b[i] < a[j]) ans++;
        }
    }
    int m = gcd(num, ans);
    num /= m;
    ans /= m;
    printf("%d/%d\n", ans, num);
}

int main() {
    int t = 1;
//    scanf("%d", &t);
    while (t--) run();
    return 0;
}

H - Needle

solved by Tryna.(-)

题意： 给出三个数组a[i],b[j],c[k]a[i], b[j], c[k]，求满足a[i]+c[k]=2∗b[j]a[i] + c[k] = 2 * b[j]的三元组(i,j,k)(i, j, k)的个数

题解：

  • 因为n很大，暴力O(n2)O(n^2)肯定会超时，考虑多项式乘法。把a,ca,c数组当做两个多项式中的次数，然后看2∗b2 * b作为次数在多项式中的系数的值即可，累加就是答案
  • 多项式乘法中，次数需为非负数，所以我们将次数的范围从−30000-30000 ~ 3000030000 更改为 00 ~ 6000060000，对于多项式乘法，我们用FFTFFT来加速实现
  • 例：样例二中：
    a：x30004a：x^{30004} x29997x^{29997} x30002x^{30002}
    b:x30004b: x^{30004} x30001x^{30001}
    c:x29997c: x^{29997} x30004x^{30004} x30000x^{30000}
    答案就为aa中第一项乘cc中第二项的系数加上aa中第三项乘cc中第三项的系数
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
// #include<bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-8;
const int maxn = 5e5 + 10;
// const int mod = 1e9 + 7;
const int mod = 998244353;
struct complex{
    double x,y;
    complex (double xx = 0, double yy = 0){x = xx, y = yy;}
}a[maxn],c[maxn];
int b[maxn];
complex operator + (complex a,complex b){ 
	return complex(a.x + b.x, a.y + b.y);
}
complex operator - (complex a,complex b){ 
	return complex(a.x - b.x, a.y - b.y);
}
complex operator * (complex a,complex b){ 
	return complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
int n, m, u;
int l, r[maxn];
int limit = 1;
void fast_fast_tle(complex *A, int type)
{
    for(int i=0;i<limit;i++) 
        if(i<r[i]) swap(A[i],A[r[i]]);//求出要迭代的序列 
    for(int mid=1;mid<limit;mid<<=1)//待合并区间的中点
    {
        complex Wn( cos(Pi/mid) , type*sin(Pi/mid) ); //单位根 
        for(int R=mid<<1,j=0;j<limit;j+=R)//R是区间的右端点，j表示前已经到哪个位置了 
        {
            complex w(1,0);//幂 
            for(int k=0;k<mid;k++,w=w*Wn)//枚举左半部分 
            {
                 complex x=A[j+k],y=w*A[j+mid+k];//蝴蝶效应 
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
        }
    }
}
void solve() {
	scanf("%d", &n);
	ll num;
	ll c1 = 0, c2 = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &num);
		a[num + 30000] = 1;
		c1 = max(c1, num + 30000);
	}
	scanf("%d", &m);
	for(int i = 1; i <= m; i++) {
		scanf("%lld", &num);
		b[i] = num + 30000;
	}
	scanf("%d", &u);
	for(int i = 1; i <= u; i++) {
		scanf("%lld", &num);
		c[num + 30000] = 1;
		c2 = max(c2, num + 30000);
	}
	while(limit <= c1 + c2) limit <<= 1, l++;
	for(int i = 0; i < limit; i++)
        r[i] = ( r[i>>1]>>1 )| ( (i&1)<<(l-1) ) ;
    // 在原序列中 i 与 i/2 的关系是 ： i可以看做是i/2的二进制上的每一位左移一位得来
    // 那么在反转后的数组中就需要右移一位，同时特殊处理一下复数 
	fast_fast_tle(a, 1);
    fast_fast_tle(c, 1);
    for(int i = 0; i <= limit; i++) a[i] = a[i] * c[i];
    fast_fast_tle(a, -1);
	ll ans = 0;
	for(int i = 1; i <= m; i++)
		ans += (int)(a[2 * b[i]].x / limit + 0.5);
	printf("%lld\n", ans);
}

int main() {
 	// freopen("1.out","w",stdout);
	int t = 1;
	// scanf("%d", &t);
	// cin>>t;
	while(t--)
		solve();
	return 0;
}

J. Switches

题意： 给出一个n∗nn * n的矩阵，每一行代表一个开关，一个开关控制若干盏灯，11对该灯进行操作，00不操作。问对于每一盏灯，是否有一个方案使得只有该盏灯亮

题解：

  • 设矩阵An∗nA_{n * n}为开关与灯的关系，矩阵B1∗nB_{1*n}为灯的亮灭情况，矩阵C1∗nC_{1*n}为开关的状态，CC矩阵即为所求答案，则有C1∗n∗An∗n=BC_{1*n} * A_{n * n} = B
文章目录
  1. B - Commemorative Dice
  2. H - Needle
  3. J. Switches
|