给定\([l, r]\) 求出在这个区间内的两个数字a和b的取模的最大值 (\(a \ge b\))
上届确定 因此我们最大的取模的值就是 \(\frac {r}{2} + 1\)
但是这个值能取到的条件是\(\frac {r}{2} + 1 \ge l\)
如果上述条件不满足 很显然答案的区间是\([0, r-l]\)
#include <bits/stdc++.h> using namespace std; inline void solve() { int l, r; cin >> l >> r; int p = max(l, r / 2 + 1); cout << r % p << endl; } signed main() { int T = 1; scanf("%d",&T); while(T -- ) solve(); return 0; }
给一个长度 \(\le 50\) 的数字, 问最多可以删除多少为使得它变成一个非质数 数据保证一定有解
首先我们可以知道 长度最短的非质数 是 1,4,6,8,9 因此我们首先特判这五个数字
其次呢, 剩下没有被使用过的数字就只有2,3,5,7 首先我们的出两个数字的所有组合(三位数以及更高位一定包含两位数,我们需要最短的
22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77 里面的质数只有23,37,53,73
因为保证一定有解, 因此我们可以排除两位数字中23,37,53,73 出现的可能, 而三位及以上的数字一定包含其他的数字
就在两位数字中的非质数 中包含了
因此所有存在的结果就只有1,4,6,8,9,22,25,27,32,33,35,52,55,57,72,75,77
一位数判断是否出现过 两位数for循环扫一遍即可
#include <bits/stdc++.h> using namespace std; int vis[1000]; int cnt[10]; inline void solve() { for(int i = 1; i < 10; i ++ ) cnt[i] = 0; int n; string a; cin >> n >> a; for(auto c : a) cnt[c - '0'] ++; for(int i = 1; i < 10; i ++ ) { if(cnt[i] && vis[i]) { cout << 1 << endl; cout << i << endl; return; } } for(int i = 0; i < n; i ++ ) for(int j = i + 1; j < n; j ++ ) { int p = a[i] - '0', q = a[j] - '0'; int res = p * 10 + q; if(vis[res]) { cout << 2 << endl; cout << res << endl; return; } } } signed main() { vis[1] = true; vis[4] = true; vis[6] = true; vis[8] = true; vis[9] = true; vis[22] = true; vis[25] = true; vis[27] = true; vis[32] = true; vis[33] = true; vis[35] = true; vis[52] = true; vis[55] = true; vis[57] = true; vis[72] = true; vis[75] = true; vis[77] = true; int T = 1; scanf("%d",&T); while(T -- ) { solve(); } return 0; }
给定一个01 串,长度为len 从中找出两个长度 \(\ge len / 2\) 的 子串
使得二者转为十进制以后具有整数倍关系
思维题(想到就很简单
我们可以把原来的字符串分为两种 有0的和没有0的
#include <bits/stdc++.h> #define rep(i, b, s) for(register int i = (b); i <= (s); ++i) using namespace std; inline void solve() { int n; string x; cin >> n >> x; int px = n / 2; rep(i, 0, n - 1) { if(x[i] == '0') { if(i >= px) { printf("1 %d 1 %d \n", i + 1, i); return; } else { printf("%d %d %d %d\n", i + 1, n, i + 2, n); return; } } } printf("%d %d %d %d\n", 1, px, 2, px + 1); } signed main() { int T = 1; scanf("%d",&T); while(T -- ) { solve(); } return 0; }
给定一个由+- 构成的字符串 +代表 1 - 代表 -1 (即代表\(a_i\)的值
规定一个子区间的值为 \(\sum_{i = l}^{r}(-1)^{i-1}a_i\)
规定一个操作为: 删去字符串中某个字符,其他的字符顺次往前移动
给定一个子区间\([l,r]\) 求出最少要进行几次操作,才能使这个区间的值为0
#include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define mk make_pair #define fix(a) fixed << setprecision(a) #define debug(x) cout<<#x" ----> "<<x<<endl #define rep(i, b, s) for(register int i = (b); i <= (s); ++i) #define pre(i, b, s) for(register int i = (b); i >= (s); --i) //#define int long long #define endl '\n' #define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0) #define all(v) (v).begin(),(v).end() using namespace std; typedef unsigned long long ULL; typedef pair<int, int> PII ; typedef pair<int, PII> PIII ;// {value, {value, value}} typedef pair<double, double> PDD ; typedef long long LL; const int INF = INT_MAX; const LL INFF = INT64_MAX; const int mod = 1e9 + 7; const double eps = 1e-10; const double pi = acos(-1.0); inline int lowbit(int x){return x&-x;} inline int gcd(int a, int b) {return b ? gcd(b, a%b) : a;} inline LL ksm(LL a, LL b) {if (b == 0) return 1; LL ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;} inline LL lcm(LL a, LL b) {return a / gcd(a, b) * b;} inline void out(bool flag); template < typename T > inline void read(T &x) { x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)){f ^= !(ch ^ 45);ch=getchar();} while(isdigit(ch)) x= (x<<1)+(x<<3)+(ch&15),ch=getchar(); x = f ? -x : x; } inline void solve() { int n, m; cin >> n >> m; vector<int> a(n + 1), s(n + 1); for(int i = 1; i <= n; i ++ ) { char cc; cin >> cc; if(cc == '+') a[i] = 1; else a[i] = -1; } rep(i, 1, n) { if(i % 2 == 1) s[i] = s[i - 1] + a[i]; else s[i] = s[i - 1] - a[i]; } rep(i, 1, m) { int l, r; cin >> l >> r; int t = abs(s[r] - s[l - 1]); if(!t) cout << 0; else if(t & 1) cout << 1; else cout << 2; cout << endl; } } signed main() { ios; int T = 1; cin >> T; while(T -- ) { solve(); } return 0; } inline void out(bool flag) { if(flag) puts("YES"); else puts("NO"); }