省选模拟 19/09/21

省选模拟 19/09/21

​​lcm​​​

#include#define N 2005#define M 205using namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = (cnt<<1) + (cnt<<3) + (ch-'0'), ch = getchar(); return cnt * f;}typedef long long ll;const int Mod = 1000000007;ll add(ll a, ll b){ return a + b >= Mod ? a + b - Mod : a + b;}ll mul(ll a, ll b){ return a * b % Mod;}void Add(int &a, int b){ a = add(a, b);}ll power(ll a, ll b){ ll ans = 1; for(;b;b>>=1){if(b&1) ans = mul(ans, a); a = mul(a, a);} return ans;}int n, a[N];int prim[41]={ 17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,1};int f[8][5][4][3][3][3], g[8][5][4][3][3][3], sum[8][5][4][3][3][3];vector v[41];int main(){ n = read(); for(int i = 1; i <= n; i++) a[i] = read(); for(int i = 1; i <= n; i++){ for(int j = 0; j < 41; j++) if(a[i] % prim[j] == 0){ a[i] /= prim[j]; v[j].push_back(a[i]); break; } } f[0][0][0][0][0][0] = 1; int ans = 0; for(int i = 40; i >= 0; i--){ if(!v[i].size()) continue; memset(sum, 0, sizeof(sum)); for(int j = 0; j < v[i].size(); j++){ memset(g, 0, sizeof(g)); int b1 = 0, b2 = 0, b3 = 0, b4 = 0, b5 = 0, b6 = 0; int now = v[i][j], delta = 1; while(now % 2 == 0) now /= 2, ++b1; while(now % 3 == 0) now /= 3, ++b2; while(now % 5 == 0) now /= 5, ++b3; while(now % 7 == 0) now /= 7, ++b4; while(now % 11 == 0) now /= 11, ++b5; while(now % 13 == 0) now /= 13, ++b6; for(int k = 0; k < b1; k++) delta *= 2; for(int a1 = 0; a1 < 8; a1++){ for(int k = 0; k < b2; k++) delta *= 3; for(int a2 = 0; a2 < 5; a2++){ for(int k = 0; k < b3; k++) delta *= 5; for(int a3 = 0; a3 < 4; a3++){ for(int k = 0; k < b4; k++) delta *= 7; for(int a4 = 0; a4 < 3; a4++){ for(int k = 0; k < b5; k++) delta *= 11; for(int a5 = 0; a5 < 3; a5++){ for(int k = 0; k < b6; k++) delta *= 13; for(int a6 = 0; a6 < 3; a6++){ Add(g[max(a1, b1)][max(a2, b2)][max(a3, b3)][max(a4, b4)][max(a5, b5)][max(a6, b6)] , mul(mul(delta, prim[i]), f[a1][a2][a3][a4][a5][a6])); Add(g[max(a1, b1)][max(a2, b2)][max(a3, b3)][max(a4, b4)][max(a5, b5)][max(a6, b6)] , mul(sum[a1][a2][a3][a4][a5][a6], delta)); if(a6 < b6) delta /= 13; } if(a5 < b5) delta /= 11; } if(a4 < b4) delta /= 7; } if(a3 < b3) delta /= 5; } if(a2 < b2) delta /= 3; } if(a1 < b1) delta /= 2; } for(int a1 = 0; a1 < 8; a1++) for(int a2 = 0; a2 < 5; a2++) for(int a3 = 0; a3 < 4; a3++) for(int a4 = 0; a4 < 3; a4++) for(int a5 = 0; a5 < 3; a5++) for(int a6 = 0; a6 < 3; a6++) Add(sum[a1][a2][a3][a4][a5][a6], g[a1][a2][a3][a4][a5][a6]); } for(int a1 = 0; a1 < 8; a1++) for(int a2 = 0; a2 < 5; a2++) for(int a3 = 0; a3 < 4; a3++) for(int a4 = 0; a4 < 3; a4++) for(int a5 = 0; a5 < 3; a5++) for(int a6 = 0; a6 < 3; a6++) Add(ans, sum[a1][a2][a3][a4][a5][a6]), Add(f[a1][a2][a3][a4][a5][a6], sum[a1][a2][a3][a4][a5][a6]); } cout << ans; return 0;}

​​Xor​​​

#include#define N 400050using namespace std;typedef long long ll;ll read(){ ll cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = (cnt<<1) + (cnt<<3) + (ch-'0'), ch = getchar(); return cnt * f;}int first[N], nxt[N], to[N], tot; ll w[N];void add(int x, int y, ll z){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y, w[tot] = z;}int n, m, id[N]; ll v[N];bool cmp(int a, int b){ return v[a] > v[b];}ll c[70], ans;void ins(ll v){ for(int i = 62; i >= 0; i--){ if((1ll<= 0; i--){ if((mi ^ c[i]) < mi) mi ^= c[i]; } if(mi == 0){ ans -= v[x]; return;} ans += v[x]; ins(now);}int main(){ freopen("Xor.in","r",stdin); freopen("Xor.out","w",stdout); n = read(), m = read(); for(int i = 1; i <= n; i++) v[i] = read(), id[i] = i; sort(id+1, id+n+1, cmp); for(int i = 1; i <= m; i++){ int x = read(), y = read(); ll z = read(); add(x, y, z); add(y, x, z); } for(int i = 1; i <= n; i++) FSY(id[i]); cout << ans; return 0;}

​​lis​​​

#include#define N 200050using namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = (cnt<<1) + (cnt<<3) + (ch-'0'), ch = getchar(); return cnt * f;}typedef long long ll;int n, m;struct Node{ int p, h; Node(int _p = 0, int _h = 0){ p = _p; h = _h;}}; struct cmp1{ bool operator ()(const Node &a, const Node &b){ return a.p < b.p;} };struct cmp2{ bool operator ()(const Node &a, const Node &b){ return a.h < b.h;} };typedef set::iterator Int;set S1;set S2;Node st[N]; int tot = 0, len;#define mid ((l+r)>>1)struct FSY{ int mx[N << 2]; void pushup(int x){ mx[x] = max(mx[x<<1], mx[x<<1|1]); } void modify(int x, int l, int r, int p, int v){ if(l == r){ mx[x] = v; return; } if(p <= mid) modify(x<<1, l, mid, p, v); else modify(x<<1|1, mid+1, r, p, v); pushup(x); } int query(int x, int l, int r, int L, int R){ if(L<=l && r<=R) return mx[x]; int ans = 0; if(L<=mid) ans = max(ans, query(x<<1, l, mid, L, R)); if(R>mid) ans = max(ans, query(x<<1|1, mid+1, r, L, R)); return ans; }}T1, T2;#undef midvoid ins(){ int p = read(), h = read() + m + 1; Node a = Node(p, h); tot = 0; Int it = S2.insert(a).first; S1.insert(a); while(1){ st[++tot] = *it; T1.modify(1, 1, n, it->p, 0); if(it == S2.begin()) break; --it; } for(int i = 1; i <= tot; i++){ int val = T1.query(1, 1, n, st[i].p, n) + 1; T1.modify(1, 1, n, st[i].p, val); T2.modify(1, 1, len, st[i].h, val); }}void del(){ int x = read(); tot = 0; Int it = S1.begin(); while(--x){ T2.modify(1, 1, len, it->h, 0), st[++tot] = *it++; } T1.modify(1, 1, n, it->p, 0); T2.modify(1, 1, len, it->h, 0); S1.erase(it); S2.erase(*it); for(int i = tot; i; i--){ int val = T2.query(1, 1, len, st[i].h, len) + 1; T1.modify(1, 1, n, st[i].p, val); T2.modify(1, 1, len, st[i].h, val); }}int main(){ n = read(); m = read(); len = m + 10; while(m--){ int op = read(); if(op == 1) ins(); if(op == 2) del(); cout << T1.mx[1] << '\n'; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。