Problem A PERFECT NUMBER PROBLEM
https://nanti.jisuanke.com/t/38220
题解：打表
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
//scanf("%d",&n);
printf("6\n28\n496\n8128\n33550336\n");
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem B Greedy HOUHOU
https://nanti.jisuanke.com/t/38221
Problem C Angry FFF Party
https://nanti.jisuanke.com/t/38222
题意：f(x)是斐波那契数的第x项，g(x)=f(f(x))，对于给定的n，将其表示成若干个g数的和，要求字典序最小，n<10^100000
题解：矩阵快速幂求一下f(x)，预处理前29项g(x)。
可以发现g(x)的增长速度非常快，其实在第29项就已经超出10^100000，由于后面的项差过大，所以方法基本唯一，所以就把贪心选一下，然后前几项在特判一下取个最小字典序就ok了。
JAVA版本一
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int maxn = 29;
static BigInteger []w = new BigInteger[maxn];
static int []v = new int[maxn];
public static BigInteger f(BigInteger n){
n = n.subtract(BigInteger.ONE);
BigInteger [][]a = new BigInteger[2][2];
BigInteger [][]b = new BigInteger[2][2];
BigInteger [][]c = new BigInteger[2][2];
for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) a[i][j] = BigInteger.ZERO;
a[0][0] = a[1][0] = a[0][1] = BigInteger.ONE;
for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) b[i][j] = BigInteger.ZERO;
for(int i = 0; i < 2; i++) b[i][i] = BigInteger.ONE;
while(n.compareTo(BigInteger.ZERO) > 0){
if(n.mod(new BigInteger("2")).equals(BigInteger.ONE)){
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
c[i][j] = BigInteger.ZERO;
for(int k = 0; k < 2; k++){
c[i][j] = c[i][j].add(b[i][k].multiply(a[k][j]));
}
}
}
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
b[i][j] = c[i][j];
}
}
}
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
c[i][j] = BigInteger.ZERO;
for(int k = 0; k < 2; k++){
c[i][j] = c[i][j].add(a[i][k].multiply(a[k][j]));
}
}
}
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
a[i][j] = c[i][j];
}
}
n = n.divide(new BigInteger("2"));
}
//System.out.println("len " + b[0][0].toString().length());
return b[0][0];
}
public static void main(String[] args)
{
Scanner cin = new Scanner (System.in);
for(int i = 1; i < maxn; i++){
w[i] = f(f(BigInteger.valueOf(i)));
}
// System.out.println(w[6] + " " + w[7]);
int T = cin.nextInt();
while(T > 0){
T--;
BigInteger n = cin.nextBigInteger();
int tot = 0;
for(int i = maxn - 1; i > 0; i--){
if(n.equals(new BigInteger("5")) && i >= 4){
v[tot++] = 4;
v[tot++] = 3;
v[tot++] = 2;
v[tot++] = 1;
n = BigInteger.ZERO;
break;
}
if(n.equals(new BigInteger("4")) && i >= 4){
v[tot++] = 4;
v[tot++] = 2;
v[tot++] = 1;
n = BigInteger.ZERO;
break;
}
if(n.equals(new BigInteger("3")) && i >= 3){
v[tot++] = 3;
v[tot++] = 2;
v[tot++] = 1;
n = BigInteger.ZERO;
break;
}
if(n.equals(new BigInteger("2")) && i >= 2){
v[tot++] = 2;
v[tot++] = 1;
n = BigInteger.ZERO;
break;
}
if(n.equals(new BigInteger("1")) && i >= 1){
v[tot++] = 1;
n = BigInteger.ZERO;
break;
}
if(n.compareTo(w[i]) >= 0){
v[tot++] = i;
n = n.subtract(w[i]);
}
}
if(!n.equals(BigInteger.ZERO)) System.out.println(-1);
else{
for(int i = tot - 1; i >= 0; i--) System.out.printf("%d%c", v[i], i == 0 ? '\n' : ' ');
}
}
cin.close();
}
}
Problem D Match Stick Game
https://nanti.jisuanke.com/t/38223
题解：
先将表达式表示成用最少火柴棍能表达的形式，然后在此基础上添加火柴棍。
先预处理出i位数添加j个火柴棍能够得到的最大值，然后背包一下就ok了。
举个例子
1+1+222
最简表示1-1-111，剩余11根棒子。
一共三项，1，-1，-111，然后dp[i][j]表示前i项加j根棒子的和的最大值，转移显然。
关键是预处理比较麻烦。
#include <bits/stdc++.h>
#define my_max(a, b) ((a) > (b) ? (a) : (b))
#define my_min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rep(i, s, t) for(int i = (int)(s); i <= (int)(t); i++)
#define rev(i, t, s) for(int i = (int)(t); i >= (int)(s); i--)
#define lson rt << 1
#define rson rt << 1 | 1
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double lb;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
typedef std::vector<int> VI;
typedef std::vector<ll> VL;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> rbtree;
ll gcd(ll x, ll y){ return y % x == 0 ? x : gcd(y % x, x); }
template<class T>T my_abs(T a){ if(a < 0) a = -a; return a; }
inline ll read(){
ll ret = 0, sign = 1;
char c = getchar();
while(c < '0' || c > '9'){ if(c == '-') sign = -1; c = getchar();}
while(c >= '0' && c <= '9'){ ret = ret * 10 + c - '0'; c = getchar(); }
return ret * sign;
}
inline void write(ll x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
//void expand_stack_space(){
// int size = 256 << 20; // 256MB
// char *p = (char*)malloc(size) + size;
// __asm__("movl %0, %%esp\n" :: "r"(p));
//}
const int maxn = 100 + 7;
const ll inf = 1e18;
ll dp[maxn][maxn * 10], sa[maxn];
ll a[maxn][maxn], b[maxn][maxn];
int n;
char str[maxn];
int count(char c){
if(c == '-' || c == '1') return 0;
if(c == '7' || c == '+') return 1;
if(c == '4') return 2;
if(c == '2' || c == '3' || c == '5') return 3;
if(c == '0' || c == '6' || c == '9') return 4;
if(c == '8') return 5;
}
char icount(int c){
if(c == 1) return '7';
if(c == 2) return '4';
if(c == 3) return '5';
if(c == 4) return '9';
if(c == 5) return '8';
}
void init(){
for(int i = 1; i <= 10; i++){
for(int j = 0; j <= 5 * i; j++){
int c = j;
string s = "";
for(int k = 1; k <= i; k++){
if(c >= count('9')) s += '9', c -= count('9');
else if(c >= count('7')) s += '7', c -= count('7');
else s += '1';
}
for(int k = i; k >= 1; k--){
if(c == 0) break;
c += count(s[k - 1]);
if(c >= count('8')) s[k - 1] = '8', c -= count('8');
else{
s[k - 1] = icount(c);
c = 0;
}
}
ll res = 0;
//cout<<"s " + s<<endl;
for(char ss : s) res = res * 10 + ss - '0';
a[i][j] = res;
b[i][j + 1] = res;
}
b[i][0] = -b[i][1];
}
}
int main(){
#ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
int T;
init();
scanf("%d", &T);
while(T--){
scanf("%d", &n);
scanf("%s", str);
int cnt = 0;
for(int i = 0; i < n; i++) cnt += count(str[i]);
int num = 0, tot = 0;
for(int i = 0; i < n; i++){
if(str[i] == '-' || str[i] == '+'){
sa[++tot] = num;
num = 0;
}
else num++;
}
//printf("cnt %d\n", cnt);
sa[++tot] = num;
for(int i = 0; i <= tot; i++) for(int j = 0; j <= cnt; j++) dp[i][j] = -inf;
//比赛时初始化写错了， 还过了。emmmm
dp[0][0] = 0;
for(int i = 1; i <= tot; i++){
int len = sa[i];
//printf("len %d\n", len);
if(i == 1){
for(int k = 0; k <= 5 * len; k++){
for(int j = cnt; j >= k; j--){
dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + a[len][k]);
}
}
}
else{
for(int k = 0; k <= 5 * len; k++){
for(int j = cnt; j >= k; j--){
dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + b[len][k]);
}
}
}
}
printf("%lld\n", dp[tot][cnt]);
}
return 0;
}
Problem E Card Game
https://nanti.jisuanke.com/t/38224
Problem F Information Transmitting
https://nanti.jisuanke.com/t/A2254
Problem G tsy's number
https://nanti.jisuanke.com/t/38226
题解：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef unsigned int ll;
const int N = 1e7 + 10;
int prime[N], phi[N], tot;
ll f[N], gg[N], fu[N], res[N];
bool is_prime[N];
void init() {
memset(is_prime, true, sizeof(is_prime));
for (ll i = 1; i < N; i++)
f[i] = f[i - 1] + 1;
for (ll i = 1; i < N; i++) {
gg[i] = gg[i - 1] + i;
f[i] = f[i] * gg[i];
}
for (ll i = 1; i < N; i++) {
gg[i] = gg[i - 1] + i * i;
f[i] = f[i] * gg[i];
}
phi[1] = gg[1] = fu[1] = 1;
for (int i = 2; i < N; i++) {
if (is_prime[i]) {
prime[tot++] = i;
fu[i] = i;
phi[i] = i - 1;
gg[i] = i - 2;
}
for (int j = 0; j < tot && i * prime[j] < N; j++) {
is_prime[i * prime[j]] = false;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
fu[i * prime[j]] = fu[i] * prime[j];
if (fu[i] == i) {
gg[i * prime[j]] = phi[i * prime[j]] - phi[i];
}else {
gg[i * prime[j]] = gg[i / fu[i]] * gg[fu[i * prime[j]]];
}
break;
}else {
fu[i * prime[j]] = prime[j];
phi[i * prime[j]] = phi[i] * phi[prime[j]];
gg[i * prime[j]] = gg[i] * gg[prime[j]];
}
}
}
for (ll i = 1; i < N; i++) {
res[i] = i * i * i * gg[i] + res[i - 1];
}
}
int n;
void solve() {
ll ans = 0;
for (ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ans += (res[r] - res[l - 1]) * f[n / l];
}
printf("%d\n", ans % (1 << 30));
}
int main() {
//freopen("0in.txt", "r", stdin);
init();
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
solve();
}
return 0;
}
Problem H Coloring Game
https://nanti.jisuanke.com/t/38227
题解：快速幂+规律
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
ll POW(ll a,ll b,ll c){
ll res=1;
ll base=a%c;
while(b){
if(b&1)res=(res*base)%c;
base=(base*base)%c;
b>>=1;
}
return res;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d",&n);
if(n==1){
cout<<1<<endl;
return 0;
}
cout<<(4*POW(3,n-2,MOD))%MOD<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem I Max answer
https://nanti.jisuanke.com/t/38228
题意：求区间最小值×区间和的最大值。
题解：用单调栈维护以每个数为最小值能拓展到最左边和最右边。然后用线段树维护一个前缀和。
对于一个数如果是正数查询当前位置到最右端的前缀和最大值，然后查询最左端到当前点的最小值做减法。
对于一个数如果是负数查询正好和上述情况相反。
C++版本一
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define sca(x) scanf("%d",&x)
#define N 500005
const LL inf = 1e18;
int a[N],L[N],R[N];
LL sum[N];
stack<int>S;
struct node
{
LL mmax,mmin;
}T[N*4];
void build(int rt,int l,int r)
{
if(l==r)
{
T[rt].mmax=sum[l];
T[rt].mmin=sum[l];
return ;
}
int m=(l+r)>>1;
build(rt<<1,l,m);
build(rt<<1|1,m+1,r);
T[rt].mmax=max(T[rt<<1].mmax,T[rt<<1|1].mmax);
T[rt].mmin=min(T[rt<<1].mmin,T[rt<<1|1].mmin);
}
LL query_max(int rt,int l,int r,int ql,int qr)
{
if(l>=ql && r<=qr)
{
return T[rt].mmax;
}
int m=(l+r)>>1;
LL ans1=-inf,ans2=-inf;
if(ql<=m) ans1=query_max(rt<<1,l,m,ql,qr);
if(qr>m) ans2=query_max(rt<<1|1,m+1,r,ql,qr);
return max(ans1,ans2);
}
LL query_min(int rt,int l,int r,int ql,int qr)
{
if(l>=ql && r<=qr)
{
return T[rt].mmin;
}
int m=(l+r)>>1;
LL ans1=inf,ans2=inf;
if(ql<=m) ans1=query_min(rt<<1,l,m,ql,qr);
if(qr>m) ans2=query_min(rt<<1|1,m+1,r,ql,qr);
return min(ans1,ans2);
}
int main()
{
int n;
sca(n);
sum[0]=0;
for(int i=1;i<=n;i++)
{
sca(a[i]);
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
while(!S.empty()&&a[S.top()]>=a[i])S.pop();
if(S.size()==0)L[i]=0;
else L[i]=S.top();
S.push(i);
}
while(!S.empty())S.pop();
for(int i=n;i>=1;i--)
{
while(!S.empty()&&a[S.top()]>=a[i])S.pop();
if(S.size()==0)R[i]=n;
else R[i]=S.top()-1;
S.push(i);
}
build(1,0,n);
LL ans=-inf;
for(int i=1;i<=n;i++)
{
if(a[i]>=0)
{
LL ans1=query_max(1,0,n,i,R[i]);
LL ans2=query_min(1,0,n,L[i],i);
ans=max(ans,a[i]*(ans1-ans2));
}
else
{
LL ans1=query_min(1,0,n,i,R[i]);
LL ans2=query_max(1,0,n,L[i],i);
ans=max(ans,a[i]*(ans1-ans2));
}
}
cout<<ans<<endl;
}
Problem J Distance on the tree
https://nanti.jisuanke.com/t/38229
题意：给你一棵树，每条边都有一个权值，m个询问，问你从x到y的路径上有多少条边的值<=w。
题解：LCA
一边dfs一边建树，每一个点的状态是从它父亲的状态转移过来的。那么两个点之间的所有可能就是一个点到他们的lca+另一个点到他们的lca。注意存边权的话，是要存在儿子节点上的。
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int ls[maxn*40],rs[maxn*40],sum[maxn*40],rt[maxn*40];
int tot,a[maxn],b[maxn];
int n,m;
struct node
{
int to,next,wei;
}e[maxn<<1];
int head[maxn],fa[maxn][25],cnt,dep[maxn];
void add(int x,int y,int z)
{
e[cnt].to=y;
e[cnt].next=head[x];
e[cnt].wei=z;
head[x]=cnt++;
}
void update(int l,int r,int &root,int last,int val)
{
root=++tot;
ls[root]=ls[last];
rs[root]=rs[last];
sum[root]=sum[last]+1;
if(l==r)
return ;
int mid=l+r>>1;
if(mid>=val)
update(l,mid,ls[root],ls[last],val);
else
update(mid+1,r,rs[root],rs[last],val);
}
int query(int l,int r,int ql,int qr,int num)
{
if(l==r)
return sum[qr]-sum[ql];
int mid=l+r>>1;
if(num<=mid)
return query(l,mid,ls[ql],ls[qr],num);
else
{
int ans=sum[ls[qr]]-sum[ls[ql]];
ans+=query(mid+1,r,rs[ql],rs[qr],num);
return ans;
}
}
int all;
void dfs(int son,int ffa,int val)
{
dep[son]=dep[ffa]+1;
fa[son][0]=ffa;
if(son!=1)
update(1,maxn,rt[son],rt[ffa],val);
for(int i=head[son];~i;i=e[i].next)
{
int ne=e[i].to;
if(ne==ffa)
continue;
dfs(ne,son,lower_bound(b+1,b+1+all,e[i].wei)-b);
}
}
void deal(){
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z),b[i]=z;
add(x,y,z),add(y,x,z);
}
sort(b+1,b+n);
all=unique(b+1,b+n)-(b+1);
tot=0;
dfs(1,1,0);
deal();
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
z=upper_bound(b+1,b+1+all,z)-b-1;
if(z==0)
printf("0\n");
else
{
int l=lca(x,y),ans=0;
if(x!=l)
ans=query(1,maxn,rt[l],rt[x],z);
if(y!=l)
ans+=query(1,maxn,rt[l],rt[y],z);
printf("%d\n",ans);
}
}
return 0;
}
Problem K MORE XOR
https://nanti.jisuanke.com/t/38230
题解：规律
C++版本一
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define INF 0x3f3f3f3f
#define FI first
#define SE second
#define MP make_pair
#define PI pair<int,int>
#define lson l,m,rt<<1,ls,rs
#define rson m+1,r,rt<<1|1,ls,rs
#define test printf("here!!!\n")
using namespace std;
const int mx=1e5+10;
int n,m,p,q;
int qz[4][4][mx];
int hz[4][4][mx];
int a[mx];
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
memset(qz,0,sizeof(qz));
memset(hz,0,sizeof(hz));
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
}
for (int i=1;i<=n;++i)
{
for (int j=0;j<4;++j)
{
int id=(i-1)%4;
int hgf=(1+j)%4;
if (id==j)
{
qz[1][j][i]=qz[1][j][i-1]^a[i];
}
else qz[1][j][i]=qz[1][j][i-1];
if (id==j||id==hgf)
{
qz[2][j][i]=qz[2][j][i-1]^a[i];
}
else qz[2][j][i]=qz[2][j][i-1];
if (id==hgf)
{
qz[3][j][i]=qz[3][j][i-1]^a[i];
}
else qz[3][j][i]=qz[3][j][i-1];
}
}
for (int i=n;i>=1;--i)
{
for (int j=0;j<4;++j)
{
int id=(i-1)%4;
int hgf=(1+j)%4;
if (id==j)
{
hz[1][j][i]=hz[1][j][i+1]^a[i];
}
else hz[1][j][i]=hz[1][j][i+1];
if (id==j||id==hgf)
{
hz[2][j][i]=hz[2][j][i+1]^a[i];
}
else hz[2][j][i]=hz[2][j][i+1];
if (id==hgf)
{
hz[3][j][i]=hz[3][j][i+1]^a[i];
}
else hz[3][j][i]=hz[3][j][i+1];
}
}
scanf("%d",&q);
int l,r;
for (int i=1;i<=q;++i)
{
scanf("%d%d",&l,&r);
int dis=(r-l+1)%4;
int cxk=(l-1)%4;
if (dis!=0) printf("%d\n",qz[dis][cxk][n]^qz[dis][cxk][l-1]^hz[dis][cxk][r+1]);
else printf("0\n");
}
}
} C++版本二
题解：规律
打表代码：
while(1){
scanf("%d",&n);
for(int l=1;l<=n;l++){
for(int r=l;r<=n;r++){
memset(vis,0,sizeof(vis));
for(int l1=l;l1<=r;l1++){
for(int r1=l1;r1<=r;r1++){
for(int l2=l1;l2<=r1;l2++){
for(int r2=l2;r2<=r1;r2++){
for(int i=l2;i<=r2;i++){
vis[i]=!vis[i];
}
}
}
}
}
cout<<l<<" "<<r<<endl;
for(int i=1;i<=12;i++){
cout<<vis[i];
}
cout<<endl;
}
}
}
1、可以发现当区间确定时，是否取用成一个固定的规律；
2、同长度的区间，取法相同；
3、对于一定的区间取法循环节长度为4，例如【1,9】循环节1000，整个区间取法100010001，并且区间长度循环节也为4，例如长度为1的区间和长度为5的区间取法循环节相同；
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
int vis[N];
char str;
int qz[4][4][N];//第一维:取法，第二维:开始位置
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
memset(qz,0,sizeof(qz));
for(int i=1;i<=n;i++){
for(int j=0;j<4;j++){
int pos=(i-1)%4;
int dis=(j+1)%4;
if(pos==j){
qz[1][j][i]=qz[1][j][i-1]^a[i];
}else{
qz[1][j][i]=qz[1][j][i-1];
}
if(pos==j||dis==pos){
qz[2][j][i]=qz[2][j][i-1]^a[i];
}else{
qz[2][j][i]=qz[2][j][i-1];
}
if(dis==pos){
qz[3][j][i]=qz[3][j][i-1]^a[i];
}else{
qz[3][j][i]=qz[3][j][i-1];
}
}
}
scanf("%d",&m);
while(m--){
scanf("%d%d",&l,&r);
int pos=(r-l+1)%4;
int dis=(l-1)%4;
int res=qz[pos][dis][r]^qz[pos][dis][l-1];
cout<<res<<endl;
}
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本三
Problem L qiqi'tree
https://nanti.jisuanke.com/t/38231
Problem M Subsequence
https://nanti.jisuanke.com/t/38232
题解：预处理+贪心
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str[N],s[N];
int pos[N][130];
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
cin>>str+1;
scanf("%d",&n);
int len=strlen(str+1);
for(int i=0;i<128;i++){
pos[len][i]=len+1;
}
for(int i=len-1;i>=0;i--){
for(int j=0;j<128;j++){
pos[i][j]=pos[i+1][j];
}
pos[i][str[i+1]]=i+1;
}
while(n--){
scanf("%s",s);
int l=strlen(s);
int id=pos[0][s[0]];
int r=0;
while(id<=len&&r<l){
r++;
id=pos[id][s[r]];
}
//cout<<l<<" "<<r<<endl;
cout<<((r==l)?"YES":"NO")<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
京公网安备 11010502036488号