1001 Theramore
觀察以下兩種情況：
以0為例，上圖就是說，只要有兩個連續的0，我們就可以一直把它們往前移動直到移動到首位。同理只要有兩個連續的1我們就可以把它們移動到尾部。
所以可以開一個棧，順序將字符入棧，一旦遇到連續的0或者1，就把它們刪去，在首尾打下標記。
const int N=1e5+5;
int T;
char stk[N],s[N];
int top;
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s+1);
int n=strlen(s+1);
int hh=0,tt=0;
top=0;
for(int i=1;i<=n;i++){
if(!top)stk[++top]=s[i];
else{
while(stk[top]==s[i]){
if(s[i]=='1')tt+=2;
if(s[i]=='0')hh+=2;
top--; i++;
}
if(i<=n)stk[++top]=s[i];
}
}
for(int i=1;i<=hh;i++)printf("%c",'0');
for(int i=1;i<=top;i++)printf("%c",stk[i]);
for(int i=1;i<=tt;i++)printf("%c",'1');
printf("\n");
}
return 0;
}
1007 Darnassus
如果把\(|i?j|?|pi?pj|\)看作邊權，題目就是要求最小生成樹，但是兩兩之間建邊數量太多了，考慮如何優化這一過程。
可以發現，如果我們選擇\((1,2),(2,3),(3,4)....\)這些邊，最后邊長一定不會超過\(n-1\)，所以最小生成樹的邊長也都不會超過\(n-1\)。因此\(|i?j|?|pi?pj|\)的其中一部分必然小于等于\(\sqrt{n}\)，我們可以枚舉這部分邊，時間復雜度是\(O(n\sqrt{n})\)。
我們不能對邊排序，因為時間復雜度超了，考慮用鏈表記錄每個邊權對應的所有邊。
（然后加了快讀和并查集按秩合并還是超時了qwq我真沒辦法了）
const int N=5e4+5,M=N*sqrt(N);
typedef long long ll;
int T;
int n,dx;
int p[N],id[N];
int f[N],rk[N];
int top;
int h[N],idx;
int fr[M],e[M],ne[M];
inline int findx(int x){
if(f[x]!=x)return f[x]=findx(f[x]);
else return x;
}
inline void merge(int u,int v){
if(rk[u]<=rk[v])f[u]=v;
else f[v]=u;
if(rk[u]==rk[v])rk[v]++;
}
inline void adde(int u,int v,int val){
fr[idx]=u; e[idx]=v; ne[idx]=h[val]; h[val]=idx++;
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(ll x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
int main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++){
p[i]=read();
id[p[i]]=i;
h[i]=-1;
}
dx=sqrt(n);
idx=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=min(n,i+dx);j++){
int c1=abs(i-j)*abs(p[i]-p[j]);
int c2=abs(i-j)*abs(id[i]-id[j]);
if(c1<=n-1)adde(i,j,c1);
if(c2<=n-1)adde(id[i],id[j],c2);
}
}
for(int i=1;i<=n;i++){ f[i]=i; rk[i]=1;}
ll res=0;
int cnt=0;
for(int i=1;i<=n-1;i++){
for(int j=h[i];~j;j=ne[j]){
int u=fr[j],v=e[j];
u=findx(u); v=findx(v);
if(u!=v){
merge(u,v);
res+=i;
cnt++;
if(cnt>=n-1)break;
}
}
if(cnt>=n-1)break;
}
write(res);puts("");
}
return 0;
}
1005 Ironforge
std被hack了，聽說題目假了。
但是還是有可以學習的地方。關鍵詞：并查集、預處理最小質因子、二分判斷一列遞增的數中是否存在區間[l,r]中的點。
代碼參考：ygg2022 杭電多校(8) 個人題解 更新至7題 - 知乎 (zhihu.com)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int T,n,m;
int a[N],b[N];
int l[N],r[N];
int st[N],primes[N],cnt,mp[N];
vector<int>pos[N];
void min_prime(int k){
for (int i = 2; i <= 200000; i++) {
if (mp[i])continue;
for (int j = i; j <= 200000; j += i) {
if (mp[j] == 0)mp[j] = i;
}
}
}
void Prime_decom(){
for(int i=1;i<=n;i++){
int x=a[i];
while(x>1){
int p=mp[x];
while(x%p==0)x/=p;
pos[p].push_back(i);
}
}
}
bool pass(int p,int l,int r){
if(pos[p].size()==0)return 0;
else{
int x=lower_bound(pos[p].begin(),pos[p].end(),l)-pos[p].begin();
if(x<pos[p].size() && r>=pos[p][x])return 1;
else return 0;
}
return 1;
}
int main(){
min_prime(N-5);
scanf("%d",&T);
while(T--){
for(int i=1;i<=N-5;i++)pos[i].clear();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<n;i++)scanf("%d",&b[i]);
Prime_decom();
for(int i=n;i>=1;i--){
r[i]=i;
while(r[i]<n && pass(b[r[i]],i,r[i]))r[i]=r[r[i]+1];
}
for(int i=1;i<=n;i++){
l[i]=i;
if(i>1 && r[i-1]>=i){
if(pass(b[i-1],l[i],r[i])){
r[i]=r[i-1];
l[i]=l[i-1];
}
}
else{
while(1){
int flag=0;
while(l[i]>1 && pass(b[l[i]-1],l[i],r[i])){
if (i <= r[l[i] - 1]) {
r[i]=r[l[i] - 1];
l[i]=l[l[i] - 1];
break;
}
flag=1;
l[i]=l[l[i]-1];
}
while(r[i]<n && pass(b[r[i]],l[i],r[i])){
r[i]=r[r[i]+1];
flag=1;
}
if(!flag)break;
}
}
}
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
//cout<<l[x]<<' '<<r[x]<<endl;
if(l[x]<=y && r[x]>=y)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return (0-0);
}
