Burnling's Blog
0%

220803 总结

发表于 更新于

#

总之就是挂大分

顺序开题

T1 解方程：意料之中，没想到可以边读入边取模。

T2 三角形：明明暴力能拿 $40$ 分，非要人类智慧乱搞，痛失 $20$ 分

T3 游戏（屠龙勇士）：屠龙勇士反被龙屠考场上推出来式子了但是忘了 $x$ 前面有系数该怎么解于是去打暴力，盯着 $p=1$ 的 $30$ 分去的，又由于没想到剑的攻击力可以重复，开的 set 没开 multiset 痛失 $10$ 分

T4 找朋友：不知道怎么回事反正输出全是零（

T1 解方程

P2312 [NOIP2014 提高组] 解方程

因为 $N,M$ 范围都很小，所以完全可以在 $[1,M]$ 的区间内将所有的正整数 $x$ 代入方程看结果是否为 $0$

问题出在离谱的 $|a_i|\leq10^{10000}$ 上，但是因为最后只需要判断结果是否为 $0$ 即可，所以可以在模意义下做这题

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;

#define FO(name) freopen(name".in","r",stdin);freopen(name".out","w",stdout)

const int maxN = 1e6+10;
typedef long long ll;

int N,M;
ll A[maxN];
int Ans[maxN];

const int MOD = 998244353;

inline bool clc(ll x){
	int ans = 0;
	for(int i = N;i>=1;i--){
		ans = ((ans + A[i]) * x) % MOD;
	}
	ans = (ans + A[0]) % MOD;
	return ans == 0;
}

inline ll read(){
	ll x=0;int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);x=x%MOD;c=getchar();}
	return x*f;
}

int cnt;

int main(){

	scanf("%d%d",&N,&M);
	for(int i = 0;i<=N;i++) A[i] = read();
	for(int i = 1;i<=M;i++){
		if(clc(i)) Ans[++cnt] = i;
	}
	printf("%d\n",cnt);
	for(int i = 1;i<=cnt;i++) printf("%d\n",Ans[i]);
	return 0;
}

T2 三角形

P4423 [BJWC2011] 最小三角形

平面分治，可惜我不会写

人类智慧，玄学旋转，转两次更保险。

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

#define FO(name) freopen(name".in","r",stdin);freopen(name".out","w",stdout)
//#define double long double

typedef long long ll;

const int maxN = 1e6+10;

struct Point{
	double x,y;
	Point(){};
	Point(int x,int y):x((double)x),y((double)y){};
	friend bool operator < (Point A,Point B){
		if(A.x != B.x) return A.x < B.x;
        return A.y < B.y;
	}
}P[maxN];

inline double Q2p(double x){
	return x*x;
}

inline double dis(Point A,Point B){
	double t =  sqrt(Q2p(A.x-B.x)+Q2p(A.y-B.y));
	return t;
}

inline double C(int a,int b,int c){
	return dis(P[a],P[b])+dis(P[a],P[c])+dis(P[b],P[c]);
}

double ans = 1e18;

int N;

void Turn(int D){
    for(int i = 1;i<=N;i++){
        double x = P[i].x;
        double y = P[i].y;
        P[i].x = cos(D)*x-sin(D)*y;
        P[i].y = sin(D)*x+cos(D)*y;
    }
    sort(P+1,P+1+N);
    for(int i = 1;i<N-1;i++){
        for(int j = i+1;j<min(i+10,N);j++){
            for(int k = j+1;k<=min(j + 10,N);k++){
                ans = min(ans,C(i,j,k));
            }
        }
    }
}
int main(){

    srand(time(0));
	scanf("%d",&N);
	for(int i = 1;i<=N;i++){
		scanf("%lf%lf",&P[i].x,&P[i].y);
	}

	Turn(rand()%360);
    Turn(rand()%360);
	printf("%.6lf\n",ans);
	return 0;
}

T3 游戏

P4774 [NOI2018] 屠龙勇士

用 multiset 存剑的攻击力，可以得到杀每条龙用的剑的攻击力序列 $S$。

解一个同余方程组，类似

$\left{\begin{matrix}
xS_1 \equiv A_1 \pmod {p_1} \
xS_2 \equiv A_2 \pmod {p_2} \
xS_3 \equiv A_3 \pmod {p_3} \
\vdots \
xS_n \equiv A_n \pmod {p_n}
\end{matrix}\right.$

如果 $S_i=1$ 的话，可以直接用 exgcd 求解。

设前 $i-1$ 组方程的解为 $ans$ ，$M=\operatorname{lcm}(p_1,p_2,\dots,p_n)$ 。

那么前 $i$ 组同余方程的解需要满足 $S_i(ans+Mx)\equiv A_i \pmod{p_i}$

移项得 $S_iMx\equiv A_i-S_i\cdot ans \pmod {p_i}$

用 exgcd 求解 $(S_iM)x+(p_i)y=(A_i-S_i\cdot ans)$

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxN = 1e5 + 10;

#define FO(name) freopen(name".in","r",stdin);freopen(name".out","w",stdout)

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

multiset<int> Sw;
int N, M;
int A[maxN];
int P[maxN];
int S[maxN];
int T[maxN];

inline void input() {
    Sw.clear();

    scanf("%lld%lld", &N, &M);
    for (int i = 1; i <= N; i++) A[i] = read();
    for (int i = 1; i <= N; i++) P[i] = read();
    for (int i = 1; i <= N; i++) T[i] = read();
    for (int i = 1; i <= M; i++) {
        int t = read();
        Sw.insert(t);
    }
    for (int i = 1; i <= N; i++) {
        auto p = Sw.upper_bound(A[i]);
        p--;
        if (p == Sw.begin()) {
            p = Sw.lower_bound(0);
            S[i] = *p;
            Sw.erase(p);
        } else {
            S[i] = *p;
            Sw.erase(p++);
        }
        Sw.insert(T[i]);
    }
    //  for(int i = 1;i<=N;i++) printf("%d ",S[i]);
    //  printf("\n");
}

inline void exgcd(int a, int b, int &g, int &x, int &y) {
    if (b == 0) g = a, x = 1, y = 0;
    else {
        exgcd(b, a % b, g, x, y);
        int t = x;
        x = y;
        y = t - (a / b) * y;
    }
}

int ma = -1;

int exCRT() {
    int ans = 0, lcm = 1;
    int x, y, g, ATK, B, C;
    for (int i = 1; i <= N; i++) {
        ATK = (__int128)S[i] * lcm % P[i];
        B = P[i];
        C = (A[i] - S[i] * ans % P[i] + P[i]) % P[i];
        exgcd(ATK, B, g, x, y);
        x = (x % B + B) % B;
        if (C % g) return -1;
        ans += (__int128)(C / g) * x % (B / g) * lcm % (lcm *= (B / g));
        ans %= lcm;
    }
    if (ans < ma) ans += ((ma - ans - 1) / lcm + 1) / lcm;
    return ans;
}
inline bool TP1() {
    for (int i = 1; i <= N; i++) if (P[i] != 1) return false;
    return true;
}

inline int quickPow(int a, int b, int p) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

inline int CRT() {
    int M = 1;
    for (int i = 1; i <= N; i++) {
        M *= P[i];
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        int M1 = quickPow(M, P[i] - 2, P[i]);
        ans = (ans + A[i] * M * M1) % P[i];
    }
    return 0;
    //  return ans * ;
}

inline void solve() {
    input();
    ma = -1;
    for (int i = 1; i <= N; i++) {
        ma = max(ma, (int)(ceil(1.0 * A[i] / S[i])));
    }
    if(TP1()){
        printf("%lld\n",ma);
        return;
    }
    printf("%lld\n", exCRT());
}
signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) {
        solve();
    }
    return 0;
}

T4 找朋友

P7738 [NOI2021] 量子通信

跟输入杠了一个多点最后发现把 char 当 int 搁那移位，乐死我了

一旦输入写对了基本就能对了，但是会 TLE

暴力思路就是对每个新生算一遍所有人与他的友好度最后输出。

但是由于 $k \leq 15$ ，如果我们用 $16$ 个 $16$ 位整数来存储 DNA 的话，至少会有一段 DNA 是完全相同的。

用一个 vector 表示第 $i$ 组 DNA 片段 为 $j$ 的学生的编号。

对于每个转校生，先看 $16$ 组片段分别与哪些学生相同，再去计算友好值

然后就是卡常乐

函数前 inline ，快读，循环展开，优先使用位运算，用 __builtin_popcount(a^b) 计算相似度，const 定义常量等

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int maxN = 400000;
bool s[maxN + 1][256];

#define FO(name) freopen(name".in","r",stdin);freopen(name".out","w",stdout)

int lastans = 0;

inline ull myRand(ull &k1, ull &k2) {
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

inline void gen(int n, ull a1, ull a2) {
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 256; j++)
            s[i][j] = (myRand(a1, a2) & (1ull << 32)) ? 1 : 0;
}

bool s2[maxN+2];
int N, Q;
ull a1, a2;
int k;

int M[maxN+2][20];

int T[maxN+2];

const int TSY = 256*256+10;
vector<int> V[17][TSY];

inline int toInt(char c) {
    return isdigit(c) ? c - '0' : c - 'A' + 10;
}

inline int read() {
    char c = getchar();
    while (!isdigit(c)) {
        if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
        c = getchar();
    }
    while (isdigit(c)) return c - '0';
}

inline void printInBin(int x, char endline = '\n') {
    for (int i = 15; i >= 0; i--) {
        putchar((x & (1 << i)) ? '1' : '0');
    }
    if (endline) putchar(endline);
}

int popcount(int x) {

    int cnt = 0;
    for (int i = 0; i < 16; i++) {
        cnt = cnt + (((1 << i) & x) ? 1 : 0);
    }

    return cnt;
}

int a, b, c, d;
int main() {
    //  getM();
    scanf("%d%d%llu%llu", &N, &Q, &a1, &a2);
    gen(N, a1, a2);
    
//    for(int i = 0;i<16;i++){
//        for(int j = 0;j<(1<<16);j++){
//            V[i][j].resize(32);
//        }
//    }
    
    int p = 0;
    for (register int i = 1; i <= N; i++) {
        p = 0;

        for (int j = 0; j < 16; j++) {
            for (int k = 15; k >= 0; k--) {
                M[i][j] |= s[i][p++] ? (1 << k) : 0;
            }
            V[j][M[i][j]].push_back(i);
        }

    }


    while (Q--) {

        for (int i = 0; i < 16; i += 8) {

            T[i] = 0;
            a = read();
            b = read();
            c = read();
            d = read();
            T[i] = (a << 12) + (b << 8) + (c << 4) + d;
            if (lastans)T[i] = ~(T[i] | (~((1 << 16) - 1)));

            T[i + 1] = 0;
            a = read();
            b = read();
            c = read();
            d = read();
            T[i + 1] = (a << 12) + (b << 8) + (c << 4) + d;
            if (lastans)T[i + 1] = ~(T[i + 1] | (~((1 << 16) - 1)));

            T[i + 2] = 0;
            a = read();
            b = read();
            c = read();
            d = read();
            T[i + 2] = (a << 12) + (b << 8) + (c << 4) + d;
            if (lastans)T[i + 2] = ~(T[i + 2] | (~((1 << 16) - 1)));

            T[i + 3] = 0;
            a = read();
            b = read();
            c = read();
            d = read();
            T[i + 3] = (a << 12) + (b << 8) + (c << 4) + d;
            if (lastans)T[i + 3] = ~(T[i + 3] | (~((1 << 16) - 1)));
            
            T[i + 4] = 0;
            a = read();
            b = read();
            c = read();
            d = read();
            T[i + 4] = (a << 12) + (b << 8) + (c << 4) + d;
            if (lastans)T[i + 4] = ~(T[i + 4] | (~((1 << 16) - 1)));
            
            T[i + 5] = 0;
            a = read();
            b = read();
            c = read();
            d = read();
            T[i + 5] = (a << 12) + (b << 8) + (c << 4) + d;
            if (lastans)T[i + 5] = ~(T[i + 5] | (~((1 << 16) - 1)));
            
            T[i + 6] = 0;
            a = read();
            b = read();
            c = read();
            d = read();
            T[i + 6] = (a << 12) + (b << 8) + (c << 4) + d;
            if (lastans)T[i + 6] = ~(T[i + 6] | (~((1 << 16) - 1)));
            
            T[i + 7] = 0;
            a = read();
            b = read();
            c = read();
            d = read();
            T[i + 7] = (a << 12) + (b << 8) + (c << 4) + d;
            if (lastans)T[i + 7] = ~(T[i + 7] | (~((1 << 16) - 1)));
        }

        int k;
        scanf("%d", &k);
        bool flg = false;
//        for (int i = 0; i < 16; i++) {
//            if (V[i][T[i]].size()) {
//                AT = i;
//                siz = V[i][T[i]].size();
//                break;
//            }
//        }
//        if(AT == -1) goto awa;

        for (int i = 0; i < 15; i++) {
            for (int t : V[i][T[i]]) {
                int cnt = 0;
                for (register int j = 0; j < 16; j++) {
                    cnt += __builtin_popcount(M[t][j] ^ T[j]);
                    if(cnt > k) break;
                }

                if (cnt <= k) {
                    printf("1\n");
                    flg = true;
                    lastans = 1;
                    goto qwq;
                }

            }

        }qwq:{};
        if (flg) continue;
        lastans = 0;
        printf("0\n");
    }
    return 0;
}