noip模擬40
\(\color{white}{\mathbb{名之以：海棠}}\)
考場 \(t1\) 看見題意非常簡單，覺得可能是個簡單題
暴力算出幾個小樣例右端點右移的時候左端點都是單調右移的，以為具有單調性，于是想了一系列維護單調性的方法，然而拍大樣例的時候掛的很慘（又一次前一個半小時啥也沒干）
看 \(t2\)，時間不夠了寫了個 \(floyd\) 直接跳
\(t3\) 發現部分分很多，認真思考兩個特殊點，一個小時找到了能得 \(50\) 分的做法
最后 \(t1\) 又加了個退火，在暴力能跑出來的范圍內正確性還可以
出分發現 \(t1\) 捆綁測試所以 \(1\) 分也沒騙到，\(t3\) 沒考慮到逆序對可能很多沒模爆了 \(long\) \(long\)，又慘掛 \(35\)
這次難度分析再次出現重大失誤，事實證明 \(t2\) 是最可做的
以后應該增加開題前思考分析時間，并且部分分也應進行對拍
A. 送花
首先當右端點右移時最優坐決策點不是單調的，因為加入一個數后可能使一個之前位置的貢獻變小，那么原來依賴其貢獻的最優區間可能左端點左移更優
線段樹維護區間的貢獻
對于右端點右移一位的時候，將這個值上上一個位置到上一個位置的值加當前貢獻，上一個位置到這個位置的值減當前貢獻，然后線段樹維護區間最大值即可
B. 星空
首先是距離的轉化，先把坐標系旋轉45度
類似于曼哈頓轉切比雪夫距離，這道題的距離是 \(min(|x_1-x_2|,|y_1-y_2|)\)
先處理出距離為零的，用并查集合并在一起，然后按 \(x\) 和 \(y\) 分別排序后找最近點對即可
對于方案數相當于距離和答案相等的邊兩端點并查集里 \(size\) 值的乘積
代碼實現
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
int n,xx,yy,fa[maxn],siz[maxn],ans=0x3f3f3f3f,ans1=0,cnt,tot;
pair<int,int>edge[maxn];
int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
struct Node{
int x,y,id;
}p[maxn];
bool cmpx(Node a,Node b){
return a.x!=b.x?a.x<b.x:a.y<b.y;
}
bool cmpy(Node a,Node b){
return a.y!=b.y?a.y<b.y:a.x<b.x;
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x);
y=find(y);
if(x==y)return;
fa[x]=y;
siz[y]+=siz[x];
return ;
}
void add(int x,int y){
if(x>y)swap(x,y);
// cout<<x<<" "<<y<<endl;
edge[++cnt]=make_pair(x,y);
return ;
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
xx=read();
yy=read();
p[i].x=xx+yy;
p[i].y=xx-yy;
fa[i]=i;
siz[i]=1;
p[i].id=i;
}
// for(int i=1;i<=n;i++){
// cout<<"ppp "<<p[i].x<<" "<<p[i].y<<endl;
// }
sort(p+1,p+n+1,cmpx);
for(int i=1;i<=n;i++){
int j=i+1;
while((p[j].x==p[i].x||p[j].y==p[i].y)&&j<=n){
merge(p[i].id,p[j].id);
j++;
}
if(j<=n)ans=min(ans,p[j].x-p[i].x);
}
// cout<<"hhh"<<endl;
sort(p+1,p+n+1,cmpy);
for(int i=1;i<=n;i++){
int j=i+1;
while((p[j].y==p[i].y||p[j].x==p[i].x)&&j<=n){
merge(p[i].id,p[j].id);
j++;
}
if(j<=n)ans=min(ans,p[j].y-p[i].y);
}
for(int i=1;i<=n;i++){
int j=i+1;
while((p[j].y==p[i].y||p[j].x==p[i].x)&&j<=n){
j++;
}
if(j<=n&&p[j].y-p[i].y==ans)add(find(p[i].id),find(p[j].id));//cout<<"hhh "<<i<<" "<<j<<endl,
}
sort(p+1,p+n+1,cmpx);
for(int i=1;i<=n;i++){
int j=i+1;
while((p[j].x==p[i].x||p[j].y==p[i].y)&&j<=n){
j++;
}
if(j<=n&&p[j].x-p[i].x==ans)add(find(p[i].id),find(p[j].id));//cout<<"hhh "<<i<<" "<<j<<endl,
}
// for(int i=1;i<=n;i++){
// if(fa[i]==i)cout<<"hhh "<<i<<" "<<siz[i]<<endl;
// }
sort(edge+1,edge+cnt+1);
tot=unique(edge+1,edge+cnt+1)-edge-1;
for(int i=1;i<=tot;i++){
int x=edge[i].first;
int y=edge[i].second;
// cout<<"kkk "<<x<<" "<<y<<endl;
ans1+=siz[x]*siz[y];
}
cout<<ans<<endl<<ans1;
return 0;
}
C. 零一串
對于每個是 \(1\) 的位置處理一個長度為 \(T\) 的零一串，每一個是一的位置表示這一時刻這個 \(1\) 能不能左移，那么最終結果很容易能處理出來
考慮怎樣從上一個位置轉移過來：
對于第 \(i\) 個 \(1\) 如果可以在 \(j\) 的時刻左移，如果 \(i+1\) 個位置是緊鄰的，那么它只能在 \(j+1\) 時刻左移，表達在 \(01\) 串上是右移一位
如果不緊鄰，那么有幾個 \(0\) 后面的可以移幾次，相當于把 \(0!\) 串的前面幾個 \(0\) 變成 \(1\)
發現只有首尾進行操作，用隊列維護即可
對于第二問的答案，是在求每個 \(01\) 串第 \(i\) 的和
如果把矩陣拍在序列上，一定對應一段連續區間，用差分維護即可
代碼實現
#include<bits/stdc++.h>
using namespace std;
#define int long long
deque<int>q;
const int maxn=1e7+5;
const int mod=998244353;
char c[maxn];
int t,n,pos[maxn],cnt,all,dis[maxn],cf[maxn],sum[maxn],ans,num,ori;
bool ans1[maxn];
int po(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
signed main(){
// freopen("shuju.in","r",stdin);
// freopen("my.out","w",stdout);
cin>>t;
scanf("%s",c+1);
n=strlen(c+1);
for(int i=1;i<=n;i++){
if(c[i]=='1')num++;
else ori+=num;
}
ori%=mod;
for(int i=1;i<=n;i++){
if(c[i]=='1')pos[++cnt]=i;
}
for(int i=1;i<=t;i++){
q.push_back(i);
}
for(int k=1;k<=cnt;k++){
all++;
if(q.back()+all>t&&q.size())q.pop_back();
q.push_front(1-all);
for(int j=1;j<=pos[k]-pos[k-1]-1&&q.size();j++){
cf[q.front()+all]++;
cf[min(cnt-k+q.front()+all+1,t+1)]--;
q.pop_front();
}
dis[k]=t-q.size();
ans1[pos[k]-dis[k]]=1;
}
for(int i=0;i<=t;i++){
if(i)sum[i]=(sum[i-1]+cf[i])%mod;
ori+=sum[i];
ori%=mod;
ans^=(po(233,i)*ori%mod);
}
for(int i=1;i<=n;i++)cout<<ans1[i];
cout<<endl<<ans;
return 0;
}
\(\color{white}{\mathbb{知否，知否，應是綠肥紅瘦。}}\)
浙公網安備 33010602011771號