220803 总结

本文主要是介绍220803 总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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\) 即可，所以可以在模意义下做这题

#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] 最小三角形

平面分治，~~可惜我不会写~~

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

#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)\)

#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 定义常量等

#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;
}

这篇关于220803 总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

220803 总结

220803 总结

T1 解方程

T2 三角形

T3 游戏

T4 找朋友

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯