停课后的第二套所谓NOIP模拟题
这套题根据教练所说的还是应该非常的简单的，但是本人的最后的得分并不是非常的理想，主要我认为还是因为自己练习的题目还是不够，在模拟和动态规划方面还是要继续努力，多多练习。废话不多说：
(color{blue} ext {或})
(color{blue} ext {【题目描述】})
小Q非常喜欢序列和位运算。
有一天，小Q想到了一个模型：一个长度为n的非负整数序列x，满足m个条件：第i个条件为x[li] or x[li+1] or … or x[ri]=pi。他想知道是否存在一个序列满足条件，如果存在，他还要构造出一个这样的序列。
(color{blue} ext {【输入】})
第一行两个整数n,m。接下来m行每行三个整数li,ri,pi。
(color{blue} ext {【输出】})
如果存在这样的序列x，第一行输出Yes，第二行输出n个不超过230−1的非负整数表示x[1]~x[n]，否则输出一行No。
(color{blue} ext {【输入样例】})
2 1
1 2 1
(color{blue} ext {【输出样例】})
Yes
1 1
(color{blue} ext {【提示】})
【数据规模及约定】
对于30%的数据，n,m≤1000。
对于另外30%的数据，pi≤1。
对于100%的数据，n,m≤100,000，1≤li≤ri≤n，0≤pi<2^30。
(color{blue} ext {【解题思路】})
本题思路其实就是一个（或两个）线段树加上了一个模拟，本人比较菜，所以说打了两个线段树，我们首先可以先发现，如果有两个区间（假设为a和b）的或和有重复，那么我们可以非常容易的就知道，中间重复的部分c=a&b，然后这样我们对线段树进行区间的修改，最后在建立一颗线段树，用于验证答案有没有矛盾，如果有矛盾就打出No否则就是Yes。
亟待完善
AC code：
/*
Name: or
Copyright: njc
Author: Mudrobot
Date: 2018/10/15 16:23:15
Description: Segment_tree
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 100005
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{
int orz,tag,l,r,son[2];
}node[12*N];
int ans[N],n,m,root,cnt,root2,command[N],L[N],R[N];
void update(int k){node[k].orz=node[node[k].son[0]].orz|node[node[k].son[1]].orz;}
void Buildtree(int &k,int l,int r){
k=++cnt;node[k].l=l;node[k].r=r;node[k].tag=-1;
if(l==r){node[k].orz=ans[l];}
else{
int mid=(l+r)/2;
Buildtree(node[k].son[0],l,mid);Buildtree(node[k].son[1],mid+1,r);
update(k);
}
}
void andnode(int k,int val){
if(node[k].tag>=0) node[k].tag&=val;
else node[k].tag=val;
}
void pushdown(int k){
if(!k) return;
andnode(node[k].son[0],node[k].tag);
andnode(node[k].son[1],node[k].tag);
node[k].tag=-1;
}
void modify(int k,int l,int r,int val){
if(node[k].l==l&&node[k].r==r) andnode(k,val);
else{
pushdown(k);
int mid=(node[k].l+node[k].r)/2;
if(mid>=r) modify(node[k].son[0],l,r,val);
else if(mid<l) modify(node[k].son[1],l,r,val);
else modify(node[k].son[0],l,mid,val),modify(node[k].son[1],mid+1,r,val);
}
}
int query1(int k,int pos){
if(node[k].l==node[k].r&&node[k].r==pos) return node[k].tag;
else{
pushdown(k);
int mid=(node[k].l+node[k].r)/2;
if(pos<=mid) query1(node[k].son[0],pos);
else return query1(node[k].son[1],pos);
}
}
int query(int k,int l,int r){
if(node[k].l==l&&node[k].r==r) return node[k].orz;
else{
int mid=(node[k].l+node[k].r)/2;
if(r<=mid) return query(node[k].son[0],l,r);
else if(l>mid) return query(node[k].son[1],l,r);
else return query(node[k].son[0],l,mid)|query(node[k].son[1],mid+1,r);
}
}
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
scanf("%d%d",&n,&m);
Buildtree(root,1,n);
int a,b,c;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&L[i],&R[i],&command[i]);
modify(root,L[i],R[i],command[i]);
}
for(int i=1;i<=n;++i){
ans[i]=query1(root,i);
if(ans[i]==-1) ans[i]=0;
}
Buildtree(root2,1,n);
for(int i=1;i<=m;++i){
if(command[i]!=query(root2,L[i],R[i])){
printf("No");return 0;
}
}
printf("Yes
");
for(int i=1;i<=n;++i)printf("%d ",ans[i]);
//fclose(stdin);fclose(stdout);
return 0;
}
/*
2 1
1 2 1
*/
(color{blue} ext {字符串})
(color{blue} ext {【题目描述】})
小C学会了SA和SAM之后，非常激动。
他看见了两个字符串s,t，其中s只包含小写字母以及*，t只包含小写字母。
小C可以进行任意多次操作，每次选择s中的一个*，将它修改为任意多个（可以是0个）它的前一个字符。他想知道是否能将s修改为t。
请你帮小C求解这道简单字符串题。
有多组数据。
(color{blue} ext {【输入】})
第一行一个整数T表示数据组数。
每组数据两行，第一行一个字符串s，第二行一个字符串t。
(color{blue} ext {【输出】})
每组数据输出一行，如果能将s修改为t，输出Yes，否则输出No。
(color{blue} ext {【输入样例】})
2
a*
aaaa
a*
ab
(color{blue} ext {【输出样例】})
Yes
No
(color{blue} ext {【提示】})
【数据规模及约定】
对于20%的数据，|s|,|t|≤7。
对于60%的数据，|s|,|t|≤300。
对于100%的数据，T≤100，|s|,|t|≤30000。
(color{blue} ext {【解题思路】})
这道题其实就是一道非常坑的模拟题，但是注意一下细节还是非常容易AC的，我们先把每一个串分成很多个块，我们保证每一个块中所有的字母都是一样的，并且包含星号，不要忘记跟在该串后面的星号也要包含在该串中，然后后面进行一个简单的判断即可AC，细节等见下面的AC code!
AC code：
/*
Name: strinq
Copyright: njc
Author: Mudrobot
Date: 2018/10/15 15:14:00
Description: simulation
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 30005
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{
int cnt,len;
char sign;
}a[N],b[N];
int n,cnta,cntb,lena,lenb;
char sa[N],sb[N];
int init()
{
cnta=1;cntb=1;
scanf("%s",sa+1);scanf("%s",sb+1);
lena=strlen(sa+1);lenb=strlen(sb+1);
a[cnta].cnt=0;a[cnta].len=1;a[cnta].sign=sa[1];
for(int i=2;i<=lena;++i){
if(sa[i]==a[cnta].sign) a[cnta].len++;
else if(sa[i]=='*'){a[cnta].cnt++;a[cnta].len++;}
else a[++cnta].cnt=0,a[cnta].len=1,a[cnta].sign=sa[i];
}
b[cntb].cnt=b[cntb].len=1;b[cntb].sign=sb[1];
for(int i=2;i<=lenb;++i){
if(sb[i]==sb[i-1]) b[cntb].cnt++,b[cntb].len++;
else b[++cntb].cnt=b[cntb].len=1,b[cntb].sign=sb[i];
}
if(cnta!=cntb){ printf("No
"); return 0;}
for(int i=1;i<=cnta;++i){
if(a[i].cnt==0){
if(a[i].sign==b[i].sign&&a[i].len==b[i].len) continue;
if(a[i].sign!=b[i].sign||a[i].len!=b[i].len) {printf("No
");return 0;}
}
else{
if(a[i].sign==b[i].sign&&a[i].len-a[i].cnt<=b[i].len) continue;
else {printf("No
");return 0;}
}
}
printf("Yes
");return 0;
}
int main()
{
//freopen("strinq.in", "r", stdin);freopen("strinq.out", "w", stdout);
read(n); for(int i=1;i<=n;++i) init();
//fclose(stdin);fclose(stdout);
return 0;
}
/*
1
a*b**b*b*c
aaaaaaaaaabbbccc
*/
(color{blue} ext {数列})
(color{blue} ext {【题目描述】})
小Q和小C是好朋友。
小Q喜欢数列。有一天，他心血来潮，写下了三个长度均为n的数列。
小C也很喜欢数列。但是他只喜欢其中一种，波动数列。
小C把他的喜好告诉了小Q。小Q便打算找出这三个数列内的最长波动数列。
也就是说，如果我们将三个数列记做a[n][3]，他必须要构造一个二元组序列：(p[i], q[i])，使得对于任何 i>1 有：
p[i]>p[i-1]
若q[i]=0，a[p[i]][q[i]]≥a[p[i-1]][q[i-1]]
若q[i]=2，只要保持段内同向即可（就是对于连续的一段q[i]=2，要么都有a[p[i]][q[i]]≥a[p[i-1]][q[i-1]]，要么都有a[p[i]][q[i]]≤a[p[i-1]][q[i-1]]）。
小Q希望这个二元组序列尽可能长。
提示：当q[i]!=q[i-1]时，数列的增减性由q[i]而非q[i-1]决定。
【简版题意】
小Q拿到一个3×n的数组，要在每一列选一个数（或者不选），满足以下条件：
（1）如果在第一行选，那它必须大于等于上一个数
（2）如果在第二行选，那么必须小于等于上一个数
（3）如果在第三行选，对于连续的一段在第三行选的数，必须满足方向相同（都小于等于上一个数或者都大于等于上一个数）
(color{blue} ext {【输入】})
输入包含4行，第一行包含一个整数n表示数列长度，第2、3、4行每行n个整数，分别表示三个数列。
(color{blue} ext {【输出】})
输出仅包含一个整数，即最长波动数列的长度。
(color{blue} ext {【输入样例】})
6
1 2 3 6 5 4
5 4 3 7 8 9
1 2 3 6 5 4
(color{blue} ext {【输出样例】})
6
(color{blue} ext {【提示】})
【样例解释】
取第三行1 2 3（增），然后取第1行6（增），然后取第三行5 4（减），长度为6。
【数据规模和约定】
对于20%的数据，n≤10，m≤1000
对于60%的数据，n≤1000，m≤1000
对于100%的数据，n≤100,000，m≤10^9
其中m=max|a[i]|
(color{blue} ext {【解题思路】})
这道题其实是一道非常好的DP加上优化，首先在推方程的时候我们会发现第三行会有两个状态，那么这是本题的一大难点，但是如果你想到我们为我们的第三行开两个状态那么这道题相当于就被我们解决了（单调递增转移一个状态，单调递减转移另一个状态）然后我们开一个二维的DP数组，第一维存行数，第二行存位置数，然后我们从前向后依次转移，比如说第一行，就是从前面比他小的最大序列长度进行转移（三行都可以），而第二行就是从前面比他大的最大序列长度进行转移（三行都可以），第三行状态1就是从前面比他小的最大序列长度进行转移，或者从自己这一行前面比他小的最大序列长度进行转移，第三行的状态2就是从前面比他大的最大序列传长度进行转移，或者从自己这一行前面比他大的最大序列长度进行转移，这样我们就成功的设计出了一个n方的算法，那么这样做实际上是要TLE的，所以说我们考虑加一个值域线段树进行优化。然后线段树部分大家应该看代码都懂（记得动态开点或离散化，不会的可以去到我的博客中搜索“逆序对”这道题）这里不再做过多的解释，下面就上代码吧！
AC code：
/*
Name: sequence
Copyright: lvmaomao
Author: Mudrobot
Date: 2018/10/15 19:54:15
Description: Segment_tree + DP
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define L -1000000000
#define R 1000000000
#define TR 20000004
#define LL long long
#define N 100004
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{
int l,r,sum,son[2];
}node[TR];
int a[4][N],dp[5][N],n,root[3],cnt;
void update(int k){node[k].sum=max(node[node[k].son[0]].sum,node[node[k].son[1]].sum);}
void modify(int &k,int l,int r,int loc,int val){
if(!k) k=++cnt;node[k].l=l;node[k].r=r;
if(l==r&&l==loc) node[k].sum=max(node[k].sum,val);
else{
LL mid=(1ll*l+r)/2;
// LL mid=(1ll*(l+r))>>1;
if(loc<=mid) modify(node[k].son[0],l,mid,loc,val);
else modify(node[k].son[1],mid+1,r,loc,val);
update(k);
}
}
int query(int k,int l,int r){
if(!k) return 0;
if(node[k].l==l&&node[k].r==r)return node[k].sum;
else{
LL mid=(1ll*node[k].l+node[k].r)/2;
// LL mid=(1ll*(node[k].l+node[k].r))>>1;
if(r<=mid) return query(node[k].son[0],l,r);
else if(l>mid) return query(node[k].son[1],l,r);
else return max(query(node[k].son[0],l,mid),query(node[k].son[1],mid+1,r));
}
}
int main()
{
//freopen("sequence.in", "r", stdin);freopen("sequence.out", "w", stdout);
read(n);
for(int u=1;u<=3;++u) for(int i=1;i<=n;++i) read(a[u][i]);
for(int i=1;i<=n;++i){
dp[1][i]=max(query(root[0],L,a[1][i]),max(query(root[1],L,a[1][i]),query(root[2],L,a[1][i])))+1;
dp[2][i]=max(query(root[0],a[2][i],R),max(query(root[1],a[2][i],R),query(root[2],a[2][i],R)))+1;
dp[3][i]=max(query(root[0],L,a[3][i]),query(root[1],L,a[3][i]))+1;
dp[4][i]=max(query(root[0],a[3][i],R),query(root[2],a[3][i],R))+1;
modify(root[0],L,R,a[1][i],dp[1][i]);modify(root[0],L,R,a[2][i],dp[2][i]);
modify(root[1],L,R,a[3][i],dp[3][i]);modify(root[2],L,R,a[3][i],dp[4][i]);
}
printf("%d",max(max(query(root[0],L,R),query(root[1],L,R)),query(root[2],L,R)));
//fclose(stdin);fclose(stdout);
return 0;
}
/*
6
1 2 3 6 5 4
5 4 3 7 8 9
1 2 3 6 5 4
*/