這場被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"<<'\n';
continue;
}
int x = n-11,flag = -1;
forn(i,n){
if(s[i]=='8'){
flag = i;
break;
}
}
if(flag==-1){
cout<<"NO"<<'\n';
continue;
}
if(flag>x){
cout<<"NO"<<'\n';
continue;
}
cout<<"YES"<<'\n';
}
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\n");
//cout<<"? 1 2"<<'\n';
fflush(stdout);
cin>>a;
get(a);
printf("? 2 3\n");
//cout<<"? 2 3"<<'\n';
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\n");
//cout<<"? 4 5"<<'\n';
fflush(stdout);
cin>>a;
get(a);
printf("? 5 6\n");
//cout<<"? 5 6"<<'\n';
fflush(stdout);
cin>>a;
get(a);
cerr<<a<<'\n';
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("\n");
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"<<'\n';
int x;cin>>x;a.push_back(x);
cout<<"? 2 3"<<'\n';
cin>>x;a.push_back(x);
cout<<"? 3 4"<<'\n';
cin>>x;a.push_back(x);
cout<<"? 4 5"<<'\n';
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<<'\n',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<<'\n';
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<<'\n';
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<<'\n';
return 0;
}
F題留坑