无数人fst了B，我也身在其中，先开C的都太机智了
在[l,r]上取三个数a,b,c(a < b < c) 使 b不能被a整除，c不能被b整除，但c能被a整除。因为r-l<=50 , 暴力
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
LL gcd(LL a, LL b) {
if (!b) return a;
else return gcd(b, a%b);
}
int main() {
LL ll, rr;
LL l, r;
l = ll, r = rr;
scanf("%lld%lld", &l, &r);
for (LL i = l+1; i < r; i++) {
for (LL ll = l; ll < i; ll++) {
for (LL rr = i+1; rr <= r; rr++) {
if (gcd(ll, rr) != 1 && gcd(ll, i) == 1
&& gcd(i, rr) == 1) {
printf("%lld %lld %lld\n", ll, i, rr);
return 0;
}
}
}
}
printf("-1\n");
return 0;
}
从1-v中选出cn1个元素不能被x整除，cn2个元素不能被y整除，且这cn1+cn2个元素不同，求最小的v
一个数n，若n/m==k，说明1，2，3----n有k个数能被m整除，则剩n-k个数不能被m整除，本题根据这个性质对n在1到（long long）1e18 二分
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL c1, c2 ,x, y;
bool ok(LL n) {
LL a = n - n/x;
LL b = n - n/y;
LL c = n - n/x/y;
return a >= c1 && b >= c2 && c >= c1 + c2;
}
int main() {
//freopen("in.txt", "r", stdin);
scanf("%lld%lld%lld%lld", &c1, &c2, &x, &y);
LL l = 1, r = (LL)1e13;
while (l <= r) {
// LL m = (r - l) >> 1 + l;
LL m = (l+r) >> 1;
if (ok(m)) r = m - 1;
else l = m + 1;
}
printf("%lld\n", l);
return 0;
}
给出1-n的一个序列A，对于1<=i <= n-1不同的|Ai-Ai-1|的个数为k
可以构造这么一个序列： 1 n 2 n-1 3 n-2....产生了最多 n - 1个不同的数对 ，比如对于 n = 6， 序列为 ： 1 6 2 5 3 4
1 2 3 4 5 6 进行一次 操作
1 6 2 3 4 5 得到 3 个 不同的值 （5，4，1），再进行一次操作
1 6 2 5 3 4 得到 5 个不同的值 （5，4，3，2，1）
一般的， 每进行m次操作，我们能得到2*m+1个不同的值，如果想得到2*m个值，在2*m+1的基础上交换第1个和第2个元素就好了
但有一点要注意的（比赛最后一个小时被绕蒙了），比如n=5，两次操作最多有4个不同的值，如果k = 3这时候不需要交换第1，2个元素
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
const int N = (int) 1e5+1;
int A[N];
int main() {
int n, k;
scanf("%d%d", &n, &k);
int kk = k;
bool ok = false;
if (k%2 == 1) {
k = (k - 1) / 2;
}
else {
k = (k - 1) / 2 + 1;
if (kk != n-1)
ok = true;
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (i%2 == 1) A[i] = i - cnt;
if (i%2 == 0) {
if (k > 0) {
A[i] = n + 1 - A[i-1];
k--;
cnt++;
}
else A[i] = i - cnt;
}
}
if (ok) {
int tem = A[1];
A[1] = A[2];
A[2] = tem;
}
printf("%d", A[1]);
for (int i = 2; i <= n; i++)
printf(" %d", A[i]);
printf("\n");
return 0;
}
给出n个元素的一个序列A，给出m个限制，每个限制由三个数字组成，l，r，q要求A[l]&A[l+1]&...&A[r] = q如果存在这样的序列，输出A[1],A[2]......A[n]
#include <cstdio>
#include <cstring>
#define Maxbit 29
#define M 110000
const int INF = (1<<30)-1;
int n, k;
int sum[M], tree[M*4];
int l[M], r[M], q[M], a[M];
void build (int l, int r, int rt) {
if (l == r) {
tree[rt] = a[l];
return;
}
int m = (l+r)>>1;
build(l, m, rt<<1);
build(m+1, r, rt<<1|1);
tree[rt] = tree[rt<<1]&tree[rt<<1|1];
}
int query (int L, int R, int l, int r, int rt) {
if (r < L || l > R) return INF;
if (L <= l && R >= r) return tree[rt];
int m = (l+r)>>1;
return query(L, R, l, m, rt<<1) & query(L, R, m+1, r, rt<<1|1);
}
void init() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= k; i++)
scanf("%d%d%d", &l[i], &r[i], &q[i]);
for (int i = 0; i <= Maxbit; i++) {
memset(sum, 0, sizeof(sum));
for (int j = 1; j <= k; j++)
if ((q[j]>>i)&1) {
sum[l[j]]++;
sum[r[j]+1]--;
}
for (int j = 1; j <= n; j++) {
sum[j] += sum[j-1];
if (sum[j] > 0) a[j] |= 1 << i;
}
}
build(1, n, 1);
}
void solve() {
for (int i = 1; i <= k; i++)
if (query(l[i], r[i], 1, n, 1) != q[i]) {
printf("NO\n");
return;
}
printf("YES\n");
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
printf("\n");
}
int main() {
init();
solve();
return 0;
}
给出n个长度相同，由大小写字母组成的字符串。朋友随机选择其中一个字串，每次你可以问朋友他选的串的某一个位置上的字符是什么，求猜对该字符串的期望
// by tourist 研究ing
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
using namespace std;
const int BITS = 17;
const int MAX = (1 << BITS) - 1;
int kb[1 << BITS];
const int N = (1 << 21) + 10;
long long bad[N];
double f[N];
char word[777][777];
int main() {
int cnt;
scanf("%d", &cnt);
for (int i = 0; i < cnt; i++) {
scanf("%s", word[i]);
}
int n = strlen(word[0]);
for (int t = 0; t < (1 << n); t++) {
bad[t] = 0;
}
for (int i = 0; i < cnt; i++) {
for (int j = i + 1; j < cnt; j++) {
int diff = 0;
for (int k = 0; k < n; k++) {
if (word[i][k] == word[j][k]) {
diff |= (1 << k);
}
}
bad[diff] |= (1LL << i);
bad[diff] |= (1LL << j);
}
}
kb[0] = 0;
for (int i = 1; i < (1 << BITS); i++) {
kb[i] = kb[i & (i - 1)] + 1;
}
for (int t = (1 << n) - 1; t >= 0; t--) {
for (int i = 0; i < n; i++) {
if (t & (1 << i)) {
bad[t ^ (1 << i)] |= bad[t];
}
}
int p = 0;
f[t] = 0.0;
for (int i = 0; i < n; i++) {
if (!(t & (1 << i))) {
f[t] += f[t ^ (1 << i)];
p++;
}
}
if (p > 0) {
f[t] /= p;
}
f[t] += (kb[bad[t] & MAX] + kb[(bad[t] >> BITS) & MAX] + kb[(bad[t] >> (2 * BITS))]) * 1.0 / cnt;
}
printf("%.17lf\n", f[0]);
return 0;
}