【AtCoder】ARC084

时间：2022-12-07 20:48:28

C - Snuke Festival

对于每个B二分求出几个A比它小记为sum

然后对于每个C就是比它小的B的sum的和

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define pdi pair<db,int>

#define mp make_pair

#define pb push_back

#define enter putchar('\n')

#define space putchar(' ')

#define eps 1e-8

#define mo 974711

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N;

int A[MAXN],B[MAXN],C[MAXN];

int64 sum[MAXN];

void Solve() {

    read(N);

    for(int i = 1 ; i <= N ; ++i) read(A[i]);

    for(int i = 1 ; i <= N ; ++i) read(B[i]);

    for(int i = 1 ; i <= N ; ++i) read(C[i]);

    sort(A + 1,A + N + 1);sort(B + 1,B + N + 1);sort(C + 1,C + N + 1);

    for(int i = 1 ; i <= N ; ++i) {

	sum[i] = lower_bound(A + 1, A + N + 1, B[i]) - A - 1;

	sum[i] += sum[i - 1];

    }

    int64 ans = 0;

    for(int i = 1 ; i <= N ; ++i) {

	ans += sum[lower_bound(B + 1,B + N + 1,C[i]) - B - 1];

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

D - Small Multiple

一开始记了一个位数，结果开到了2000多位都WA

其实发现答案不会超过5 * 9

直接设\(dp[i][j]\)为现在答案是\(i\),\(%K\)意义下是\(j\)

每次转移往后加一位就行，就是如果加了一位\(h\)，第二维是\((10j + h) % K\)

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define pdi pair<db,int>

#define mp make_pair

#define pb push_back

#define enter putchar('\n')

#define space putchar(' ')

#define eps 1e-8

#define mo 974711

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int K;

bool dp[55][100005];

queue<int> Q;

void Solve() {

    read(K);

    for(int i = 1 ; i <= 9 ; ++i) dp[i][i % K] = 1;

    for(int i = 1 ; i <= 50 ; ++i) {

	for(int a = 0 ; a < K ; ++a) {

	    if(dp[i][a]) Q.push(a);

	}

	while(!Q.empty()) {

	    int v = Q.front();Q.pop();

	    if(!dp[i][v * 10 % K]) {

		dp[i][v * 10 % K] = 1;

		Q.push(v * 10 % K);

	    }

	}

	for(int a = 0 ; a < K ; ++a) {

	    if(!dp[i][a]) continue;

	    for(int j = 1 ; j <= 9 ; ++j) {

		if(i + j > 50) break;

		int h = (a * 10 + j) % K;

		dp[i + j][h] = 1;

	    }

	}

    }

    for(int i = 1 ; i <= 50 ; ++i) {

	if(dp[i][0]) {

	    out(i);enter;return;

	}

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

E - Finite Encyclopedia of Integer Sequences

如果K是偶数的话，答案是K / 2，K，K，K，K.....

如果K是奇数构造一个数列

K / 2 +1，K / 2 + 1，K / 2 + 1，K / 2 + 1.....

长度为N

发现一个序列

\(a_i\)映射到\(K - a_i + 1\)如果\(a_i\)不是构造出的这个序列的一个前缀，那么肯定这两个序列中，一个在这个序列前，一个在这个序列后

所以这个序列的排名是\((S + N) / 2\)

往前倒退\(N / 2\)个即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define pdi pair<db,int>

#define mp make_pair

#define pb push_back

#define enter putchar('\n')

#define space putchar(' ')

#define eps 1e-8

#define mo 974711

#define MAXN 300005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

    	if(c == '-') f = -1;

    	c = getchar();

    }

    while(c >= '0' && c <= '9') {

    	res = res * 10 + c - '0';

    	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

    	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,K;

int a[MAXN];

void Solve() {

    read(K);read(N);

    if(K % 2 == 0) {

        out(K / 2);space;

        for(int i = 2 ; i <= N ; ++i) {

            out(K);space;

        }

        enter;

    }

    else {

        for(int i = 1 ; i <= N ; ++i) a[i] = (K + 1) / 2;

        int t = N / 2;

        int p = N;

        while(t--) {

            --a[p];

            if(a[p] != 0) {

                for(int i = p + 1 ; i <= N ; i++) a[i] = K;

                p = N;

            }

            if(a[p] == 0) --p;

        }

        for(int i = 1 ; i <= N ; ++i) {

            if(a[i] != 0) {

                out(a[i]);space;

            }

        }

        enter;

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

F - XorShift

就是考虑两个多项式，它们互相消，肯定会消成0，这个消成0之前的，就是他们的gcd

所有的数肯定都是这个gcd的倍数

所以我们设gcd长度为a，x长度为b

这个数前\(b - a +1\)随便填，后面的位数可以唯一确定，所以答案就是\(x\)的前\(b - a +1\)位二进制构成的数+1

但是有个特殊的，就是如果前面恰好等于\(x\)的情况，可能后面确定好的数就超过了x，这个特判一下减掉就好

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define MAXN 100005

#define eps 1e-10

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

	res = 0;T f = 1;char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		res = res * 10 + c - '0';

		c = getchar();

	}

	res *= f;

}

template<class T>

void out(T x) {

	if(x < 0) {x = -x;putchar('-');}

	if(x >= 10) {

		out(x / 10);

	}

	putchar('0' + x % 10);

}

const int MOD = 998244353;

vector<int> num[7],x,g,t;

int N;

char s[4005];

vector<int> gcd(vector<int> a,vector<int> b) {

	if(a.size() < b.size()) swap(a,b);

	if(b.size() == 1 && b[0] == 0) return a;

	vector<int> d(a.size());

	int t = a.size() - 1;

	for(int i = b.size() - 1 ; i >= 0 ; --i) {

		d[t] = a[t] ^ b[i];

		--t;

	}

	for(int i = t ; i >= 0 ; --i) d[i] = a[i];

	while(d.size() > 1) {

		if(d.back() == 0) d.pop_back();

		else break;

	}

	return gcd(b,d);

}

void Init() {

	read(N);

	scanf("%s",s + 1);

	int len = strlen(s + 1);

	for(int i = len ; i >= 1 ; --i) {

		x.pb(s[i] - '0');

	}

	for(int i = 1 ; i <= N ; ++i) {

		scanf("%s",s + 1);

		len = strlen(s + 1);

		for(int j = len ; j >= 1 ; --j) num[i].pb(s[j] - '0');

	}

	g = num[1];

	for(int i = 2 ; i <= N ; ++i) g = gcd(g,num[i]);

}

void Solve() {

	t = x;

	if(g.size() > x.size()) {out(1);enter;return;}

	int l = x.size() - g.size() + 1;

	int d = x.size() - 1;

	int ans = 0;

	for(int i = 0 ; i < l ; ++i) {

		ans = (1LL * ans * 2 + x[d - i]) % MOD;

	}

	ans = (ans + 1) % MOD;

	for(int i = l ; i < x.size() ; ++i) t[d - i] = 0;

	for(int i = 0 ; i < l ; ++i) {

		if(t[d - i] == 1) {

			int k = g.size() - 1;

			for(int j = 0 ; j < g.size() ; ++j) {

				t[d - i - j] = t[d - i - j] ^ g[k - j];

			}

		}

	}

	for(int i = l ; i < x.size() ; ++i) {

		if(t[d - i] != x[d - i]) {

			if(t[d - i] > x[d - i]) ans = (ans + MOD - 1) % MOD;

			break;

		}

	}

	out(ans);enter;

}

int main() {

#ifdef ivorysi

	freopen("f1.in","r",stdin);

#endif

	Init();

	Solve();

}

相关文章