这场被B题坑了一小时，其他做起来都是一眼题。
A：正常模拟就好
代码：
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int main(){
IO;
int t;cin>>t;
while(t--){
int n;string s;
cin>>n>>s;
if(n<11){
cout<<"NO"<<'
';
continue;
}
int x = n-11,flag = -1;
forn(i,n){
if(s[i]=='8'){
flag = i;
break;
}
}
if(flag==-1){
cout<<"NO"<<'
';
continue;
}
if(flag>x){
cout<<"NO"<<'
';
continue;
}
cout<<"YES"<<'
';
}
return 0;
}
B题：
这题放两个思路
- 思路一：询问12 23确定1 2 3的值；询问45 56确定4 5 6的值
- 思路二：取六个数的全排列符合输出
代码一：
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
vector<int>ans,cnt;
int z[] = {32,60,64,92,168,120,128,184,336,240,345,630,368,672,966};
int x[] = {4,4,4,4,4,8,8,8,8,15,15,15,16,16,23};
int y[] = {8,15,16,23,42,15,16,23,42,16,23,42,23,42,42};
void get(int t){
forn(i,15){
if(t==z[i]){
cnt.push_back(x[i]);
cnt.push_back(y[i]);
}
}
}
int vis[100];
int main(){
int num[6]={4, 8, 15, 16, 23, 42};
int a;
printf("? 1 2
");
//cout<<"? 1 2"<<'
';
fflush(stdout);
cin>>a;
get(a);
printf("? 2 3
");
//cout<<"? 2 3"<<'
';
fflush(stdout);
cin>>a;
get(a);
forn(i,4){
vis[cnt[i]]++;
}
forn(i,4){
if(vis[cnt[i]]==1){
ans.push_back(cnt[i]);
break;
}
}
forn(i,4){
if(vis[cnt[i]]==2){
ans.push_back(cnt[i]);
break;
}
}
for(int i=3;i>=0;i--){
if(vis[cnt[i]]==1){
ans.push_back(cnt[i]);
break;
}
}
cnt.clear();
printf("? 4 5
");
//cout<<"? 4 5"<<'
';
fflush(stdout);
cin>>a;
get(a);
printf("? 5 6
");
//cout<<"? 5 6"<<'
';
fflush(stdout);
cin>>a;
get(a);
cerr<<a<<'
';
forn(i,4){
vis[cnt[i]]++;
}
forn(i,4){
if(vis[cnt[i]]==1){
ans.push_back(cnt[i]);
break;
}
}
forn(i,4){
if(vis[cnt[i]]==2){
ans.push_back(cnt[i]);
break;
}
}
for(int i=3;i>=0;i--){
if(vis[cnt[i]]==1){
ans.push_back(cnt[i]);
break;
}
}
printf("! ");
forn(i,6){
printf("%d ",ans[i]);
}
printf("
");
return 0;
}
代码二：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
int main(){
vector<int>v = {4, 8, 15, 16, 23, 42},a;
cout<<"? 1 2"<<'
';
int x;cin>>x;a.push_back(x);
cout<<"? 2 3"<<'
';
cin>>x;a.push_back(x);
cout<<"? 3 4"<<'
';
cin>>x;a.push_back(x);
cout<<"? 4 5"<<'
';
cin>>x;a.push_back(x);
do{
if(v[0]*v[1]!=a[0]) continue;
if(v[1]*v[2]!=a[1]) continue;
if(v[2]*v[3]!=a[2]) continue;
if(v[3]*v[4]!=a[3]) continue;
cout<<'!';
for(auto x:v) cout<<' '<<x;
return cout<<'
',0;
}while(next_permutation(v.begin(),v.end()));
}
C题：裸的并查集 比赛时找不到板子我手敲都5分钟写完
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 5e5+5;
int par[maxn],rankk[maxn],a[maxn];
void init(int n){
for1(i,n){
rankk[i] = 1;
par[i] = i;
}
}
int find(int x){
return par[x]==x?x:par[x] = find(par[x]);
}
void unit(int x,int y){
x = find(x),y = find(y);
if(x==y) return;
if(rankk[x]>rankk[y]) swap(x,y);
par[x] = y;
rankk[y] += rankk[x];
}
int main(){
IO;
int n,m;cin>>n>>m;
init(n);
forn(i,m){
int x;cin>>x;
forn(i,x) cin>>a[i];
for1(i,x-1) unit(a[i],a[i-1]);
}
for1(i,n) cout<<rankk[find(i)]<<' ';
cout<<'
';
return 0;
}
D题不难想出 左括号按01 右括号按01顺下去
代码：
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5+5;
int ans[maxn];
int main(){
IO;
int n;string s;cin>>n>>s;
int a =0,b=0;
forn(i,n){
if(s[i]=='('){
a++;
if(a&1) ans[i] = 0;
else ans[i] = 1;
}
else{
b++;
if(b&1) ans[i] = 0;
else ans[i] = 1;
}
}
forn(i,n) cout<<ans[i];
cout<<'
';
return 0;
}
E题 双指针
n个数 删除[1,J]满足数组不递减 肯定满足删除[1,j+1] [1,j+2]…[1,n]都满足不递减
那我们先以左端点为1，找到最小的右端点的值j，此时ans+=k-j+1
然后我们来看看[2,j]可以吗 不可以就看看[2,j+1] [2,j+2]…知道找到一个新的最小j，此时ans+=k-j+1
以此类推我们滑动双指针的复杂度为O(4*N)
因为n为1e6 每次判断必须是O1或者Ologn，这边就是这个思路的难点了
这里我是O1的，存了4个数组
- l数组记录大小为i的数第一次出现的位置
- r数组记录大小为i的数最后一次出现的位置
- L数组记录区间(i~n)大小的数第一次出现的位置
- R数组记录区间(1-i)大小的数最后一次出现的位置
这些预处理也都是On的处理
判断以1为左端点时，我只要判断L[j]是否小于r[j-1]
定左端点时：
我要确保左端点前的L[i-1]（左端点前所有的数最后一次出现的位置）
小于R[j+1]（右端点后的所有的数第一次出现的位置）
再剩下的就是细节调整了
因为我R初始化了正无穷，所以j最大为k
当j=k时 ans+=k-j+1，如果此时不符合条件就不能继续算下去了
然后我们发现如果左端点前的R[i-2]（左端点变化前的所有的数最后一次出现的位置）
大于l[i-1]（更新的这个值）那么此时操作已经无效可以终止了break。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int maxn = 1e6+5;
const int inf = 0x3f3f3f3f;
int a[maxn],l[maxn],r[maxn],L[maxn],R[maxn];
int main(){
IO;
int n,k;cin>>n>>k;
memset(l,inf,sizeof(l));
memset(L,inf,sizeof(L));
memset(r,-1,sizeof(r));
memset(R,-1,sizeof(R));
for1(i,n){
cin>>a[i];
l[a[i]] = min(i,l[a[i]]);
r[a[i]] = i;
}
for1(i,k) R[i] = max(r[i],R[i-1]);
for(int i=k;i>=1;i--) L[i] = min(l[i],L[i+1]);
int j = k;
while(j>1&&L[j+1]>=r[j]) j--;
ll ans = 0;
ans+=k-j+1;
for(int i=2;i<=k;i++){
if(R[i-2]>l[i-1]) break;
while(j<i||R[i-1]>L[j+1]) j++;
ans+=k-j+1;
}
cout<<ans<<'
';
return 0;
}
F题留坑