A.记录每个A前面有多少个Q 后面有多少个Q
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; const double EPS = 1.0e-8; const double eps = 1.0e-8; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6 + 10; const int maxm = 300; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //next_permutation int a[maxn]; int b[maxn]; int n, now, cur, pop; int main() { //freopen("in.txt", "r", stdin); int left, right; string a1; cin >> a1; int len = a1.size(); for (int i = len - 1; i >= 0; i--) { if (a1[i] == 'Q') { a[i] = a[i + 1] + 1; } else { a[i] = a[i + 1]; } } for (int i = 0; i < len; i++) { if (a1[i] == 'Q') { if (i == 0) { b[i] = 1; } else { b[i] = b[i - 1] + 1; } } else { if (i == 0) { b[i] = 0; } else { b[i] = b[i - 1]; } } } int anser = 0; for (int i = 0; i < len; i++) { if (a1[i] == 'A') { anser += a[i] * b[i]; } } cout << anser << endl; }
B.直接快速幂(n-1)*(m-1)会炸 快速幂两次/欧拉函数降幂
快速幂两次:
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; const double EPS = 1.0e-8; const double eps = 1.0e-8; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6 + 10; const int maxm = 300; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //next_permutation ll mod = 1e9 + 7; ll mod2 = mod - 1; ll quick(ll a, ll b, ll mod) { ll now = 1; while (b) { if (b % 2) { now = (now * a) % mod; } a = (a * a) % mod; b >>= 1; } return now; } int main() { ll n, m, k; cin >> n >> m >> k; if ((n == 1) || (m == 1)) { if (k == 1) { cout << 1 << endl; return 0; } else { if ((n + m) % 2) { cout << 0 << endl; return 0; } else { cout << 1 << endl; return 0; } } } ll ans = quick(2, n - 1, mod); ans = quick(ans, m - 1, mod); if (k == 1) { cout << ans << endl; } else { if ((n + m) % 2) { cout << 0 << endl; } else { cout << ans << endl; } } return 0; }
欧拉函数降幂:
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; const double EPS = 1.0e-8; const double eps = 1.0e-8; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6 + 10; const int maxm = 300; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //next_permutation ll mod = 1e9 + 7; ll mod2 = mod - 1; ll quick(ll a, ll b, ll mod) { ll now = 1; while (b) { if (b % 2) { now = (now * a) % mod; } a = (a * a) % mod; b >>= 1; } return now; } int main() { ll n, m, k; cin >> n >> m >> k; if ((n == 1) || (m == 1)) { if (k == 1) { cout << 1 << endl; return 0; } else { if ((n + m) % 2) { cout << 0 << endl; return 0; } else { cout << 1 << endl; return 0; } } } ll ans = quick(2, ((n - 1) % mod2) * ((m - 1) % mod2), mod); if (k == 1) { cout << ans % mod << endl; } else { if ((n + m) % 2) { cout << 0 << endl; } else { cout << ans % mod << endl; } } return 0; }
C:毒瘤..... 一开始的做法错误 并不是N^2检验是否全部都存在然后输出原序列就行
因为他给你的数是按得到的数的大小递增排序给出 N^2检验 两个不一定是相连的
其实只要所有数的gcd等于最小的就可以 然后再每两个数之间插入最小的数 就构造成功了
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; const double EPS = 1.0e-8; const double eps = 1.0e-8; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6 + 10; const int maxm = 300; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //next_permutation int n, now, cur, pop; ll mod = 1e9 + 7; int a[maxn]; int visit[maxn]; int flag = 0; int gcd(int x, int y) { if (y == 0) { return x; } else { return (gcd(y, x % y)); } } int main() { cin >> n; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); visit[a[i]] = 1; } int now = 0; for (int i = 1; i <= n; ++i) { now = gcd(now, a[i]); } if (now != a[1]) { cout << -1 << endl; return 0; } else { cout << n * 2 << endl; for (int i = 1; i <= n; ++i) { cout << a[i] << " " << a[1] << " "; } cout << endl; } return 0; }
D:
#include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #include <time.h> #include <stdlib.h> #include <string> #include <bitset> #include <vector> #include <set> #include <map> #include <queue> #include <algorithm> #include <sstream> #include <stack> #include <iomanip> using namespace std; #define pb push_back #define mp make_pair typedef pair<int,int> pii; typedef long long ll; typedef double ld; typedef vector<int> vi; #define fi first #define se second #define fe first #define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);} #define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);} #define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);} #define es(x,e) (int e=fst[x];e;e=nxt[e]) #define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e]) #define SZ 2333333 int n,m,l[SZ]; vector<int> vs[1000099]; ll ans[SZ]; vector<pii> qs[1000099]; inline void add_qry(int a,int b,int c) { if(c>=0) qs[b].pb(pii(a,c)); } int ts[SZ]; ll qzh[SZ]; #define UP 23333333 void dfs(int x) { if(x+x<=n) { dfs(x+x); for(auto g:vs[x+x]) if(g+l[x+x]<=UP) vs[x].pb(g+l[x+x]); vs[x+x].clear(); } if(x+x+1<=n) { dfs(x+x+1); for(auto g:vs[x+x+1]) if(g+l[x+x+1]<=UP) vs[x].pb(g+l[x+x+1]); vs[x+x+1].clear(); } vs[x].pb(0); int tn=0; for(auto g:vs[x]) ts[++tn]=g; sort(ts+1,ts+1+tn); for(int i=1;i<=tn;++i) qzh[i]=qzh[i-1]+ts[i]; for(auto q:qs[x]) { int c=q.se,u=upper_bound(ts+1,ts+1+tn,c)-ts-1; ans[q.fi]+=c*(ll)u-qzh[u]; } } int main() { scanf("%d%d",&n,&m); for(int i=2;i<=n;++i) scanf("%d",l+i); for(int i=1;i<=m;++i) { int a,b,bf=0; scanf("%d%d",&a,&b); add_qry(i,a,b); for(int g=a;g&&b>=0;bf=g,b-=l[g],g>>=1) { if(g==a) continue; ans[i]+=b; add_qry(i,bf^1,b-l[bf^1]); } } dfs(1); for(int i=1;i<=m;++i) printf("%I64d ",ans[i]); }