当前位置:网站首页>P3500 [POI2010]TES-Intelligence Test(二分&离线)
P3500 [POI2010]TES-Intelligence Test(二分&离线)
2022-07-06 04:11:00 【Harris-H】
P3500 [POI2010]TES-Intelligence Test(二分&离线)
法1
vector 存每个数对应的位置。
然后对于每个查询串的每个位置,二分找到最小> l a s t last last 的。其实序列自动机的本质就是寻找下一个最小的位置,只不过序列自动机限制了字符集大小。
时间复杂度: O ( T m l o g m ) O(Tmlogm) O(Tmlogm)
#include <cstdio>
#include <vector>
using namespace std;
int poi;
bool yes;
vector <int> a[1000010];
int b[1000010];
int dd(int now,int l,int r)
{
int ans=-1;
while (l<=r)
{
int m=(l+r)/2;
if (a[now][m]>poi)
{
ans=a[now][m];
yes=true;
r=m-1;
}
else
l=m+1;
}
return ans;
}
int main()
{
int m;
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int t;
scanf("%d",&t);
a[t].push_back(i);
}
int T;
scanf("%d",&T);
while (T--)
{
bool flag=true;
int n;
poi=0;
scanf("%d",&n);
for (int j=1;j<=n;j++)
scanf("%d",&b[j]);
for (int j=1;j<=n;j++)
{
int now=b[j];
int l=0,r=a[now].size();
if (r==0)
{
flag=false;
break;
}
r--;
yes=false;
int ttt=dd(now,l,r);
if (yes)
poi=ttt;
else
{
flag=false;
break;
}
}
if (flag)
printf("TAK\n");
else
printf("NIE\n");
}
return 0;
}
法2
可以离线做,考虑建图做,先将对应数与查询串的第一个位置连边。
然后按顺序遍历模板串的位置 i i i ,对其下一个位置进行建边。
注意要去掉前面的连边,直接 h [ i ] = 0 h[i]=0 h[i]=0。
时间复杂度: O ( n + ∑ m ) O(n+\sum m) O(n+∑m)
// SeptEtavioxy
#include<cstdio>
#include<cctype>
#include<cstring>
#define re register
#define ll long long
#define il inline
#define rep(i,s,t) for(re int i=(s);i<=(t);i++)
#define pt(ch) putchar(ch)
#define pti(x) printf("%d",x)
using namespace std;
// c_ints
il int ci(){
re char ch;
while(!isdigit(ch=getchar()));
re int x= ch^'0';
while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
return x;
}
enum{
N=1000024};
class node{
public:
int nxt,pos;//pos是所属的序列id
}bow[N];
int tot;
int head[N];
il void add(int x,int y){
bow[++tot].nxt= head[x];
bow[tot].pos= y;
head[x]= tot;
}//邻接表,bow[x]表示数字x上的询问
int a[N];
int k[N],*p[N];
int d[N*2],*last=d;//指针存储
int cur[N];//询问序列当前位置
bool ok[N];//答案
int main(){
int m= ci();
rep(i,1,m) a[i]= ci();
int n= ci();
rep(i,1,n){
k[i]= ci();
//p[i]= last;
p[i] = new int[k[i]+1];
rep(j,1,k[i]) p[i][j]= ci();
//last+= k[i]+1;
add(p[i][1],i);//加入首项
}
rep(i,1,m){
int u= a[i];
int j= head[u];
head[u]= 0;//清除邻接表
for(;j;j=bow[j].nxt){
int t= bow[j].pos;
if( ++cur[t] == k[t] ) ok[t]= 1;//成功匹配
else add(p[t][cur[t]+1],t);//加入下一位
}
}
rep(i,1,n) puts(ok[i]?"TAK":"NIE");
return 0;
//end面()
}
边栏推荐
- Network security - Security Service Engineer - detailed summary of skill manual (it is recommended to learn and collect)
- Thread sleep, thread sleep application scenarios
- Custom event of C (31)
- hashlimit速率控制
- PTA tiantisai l1-078 teacher Ji's return (15 points) detailed explanation
- 2/12 didn't learn anything
- Scalpel like analysis of JVM -- this article takes you to peek into the secrets of JVM
- 软考 系统架构设计师 简明教程 | 总目录
- 【leetcode】1189. Maximum number of "balloons"
- Global and Chinese markets for fire resistant conveyor belts 2022-2028: Research Report on technology, participants, trends, market size and share
猜你喜欢
Lora gateway Ethernet transmission
Basic knowledge of binary tree, BFC, DFS
Scalpel like analysis of JVM -- this article takes you to peek into the secrets of JVM
Detailed explanation of serialization and deserialization
MySQL master-slave replication
Data processing methods - smote series and adasyn
Solution to the problem that the root account of MySQL database cannot be logged in remotely
1291_ Add timestamp function in xshell log
关于进程、线程、协程、同步、异步、阻塞、非阻塞、并发、并行、串行的理解
绑定在游戏对象上的脚本的执行顺序
随机推荐
综合能力测评系统
Facebook and other large companies have leaked more than one billion user data, and it is time to pay attention to did
asp. Core is compatible with both JWT authentication and cookies authentication
MySQL transaction isolation level
Ks008 SSM based press release system
Web components series (VII) -- life cycle of custom components
Network security - Security Service Engineer - detailed summary of skill manual (it is recommended to learn and collect)
POI add border
10个 Istio 流量管理 最常用的例子,你知道几个?
IDEA编译JSP页面生成的class文件路径
使用JS完成一个LRU缓存
One question per day (Mathematics)
Benefits of automated testing
10 exemples les plus courants de gestion du trafic istio, que savez - vous?
Tips for using dm8huge table
Basic knowledge of binary tree, BFC, DFS
pd. to_ numeric
When debugging after pycharm remote server is connected, trying to add breakpoint to file that does not exist: /data appears_ sda/d:/segmentation
P2648 make money
C form application of C (27)