（某咕咕咕的人在咕咕咕了咕咕咕天之后，又準備開始寫博客了）
今天得分：30+0+0，T3算錯了空間，50分沒了，，，
T1
題目大意：一個圓上有3n個不同的點，每個點都被染成了n種顏色中的一種，每種顏色恰好出現了3次，對每種顏色畫一條圓弧，滿足其兩端點的顏色都是c且不經過另一個顏色為c的點，要求這n條圓弧互不相交，求畫圓弧的方案數，n<=2e5
題解：容易發現，該圖最多選擇的圓弧數為n，于是我們只需要求最大匹配的方案數，隨便dp即可，關于環轉化成鏈，我們只需要列舉第一個點的那種顏色選擇圓弧的方法，就可以不重不漏統計方案，時間復雜度O(N)，
AC代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
inline int re_ad()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
const int mo=998244353;
int n,n3,n6,ans;
int a[1200010],las[1200010],pla[200010],to[1200010];
struct node{int num;int ans;}dp[1200010];
inline int jia(int x,int y){x+=y;if(x>=mo)x-=mo;return x;}
inline void solve(int bg,int fro)
{
register int i,j;//cout<<" "<<bg<<" "<<fro<<endl;
memset(dp,0,sizeof(dp));
dp[fro-bg]=(node){1,1};
for(i=fro-bg+1;i<=n3;++i)
{
dp[i]=dp[i-1];
if(las[bg+i]>bg)
{
if(dp[las[bg+i]-bg-1].num+1>dp[i].num){dp[i]=dp[las[bg+i]-bg-1];++dp[i].num;}
else if(dp[las[bg+i]-bg-1].num+1==dp[i].num)dp[i].ans=jia(dp[i].ans,dp[las[bg+i]-bg-1].ans);
}//cout<<i<<" "<<i+bg<<" "<<dp[i].num<<" "<<dp[i].ans<<endl;
}
if(dp[n3].num==n)ans=jia(ans,dp[n3].ans);
}
int main()
{
freopen("arc.in","r",stdin);
freopen("arc.out","w",stdout);
register int i,la=0;
n=re_ad();n3=n*3;n6=n3*2;
for(i=1;i<=n3;++i)a[i]=a[i+n3]=re_ad();
for(i=1;i<=n6;++i)
{
las[i]=pla[a[i]];to[pla[a[i]]]=i;
pla[a[i]]=i;
}
solve(0,to[1]);
solve(to[1]-1,to[to[1]]);
solve(to[to[1]]-1,n3+1);
cout<<ans<<endl;return 0;
//for(i=1;i<=n6;++i)cout<<i<<" "<<las[i]<<endl;
}T2
題目大意：求有多少個正整數x滿足c[0]*x^a[0]+c[1]*x^a[1]+...+c[n-1]*x^a[n-1]能被x^0+x^1+...+x^(m-1)整除，其中c和a是兩個給定的序列，n<=1e5,m,ai<=1e9,|ci|=1 ，
題解：特判x=1，之后把原式變成f(x)*(x-1) mod (x^m-1)，得到取模之后的式子后，設每一項的系數為ki，則我們只需要判斷在2-max(ki+1)范圍內的數即可，判斷x0的時候，對于ki>=x0的部分，k[i]-=x0,k[(i+1)%m]++;對于ki<=-x0的部分，k[i]+=x0,k[(i+1)%m]--;最后判斷最終的ki是否全等于0或全等于1-x0或全等于x0-1即可，由于每次操作ki的絕對值減少x0-1，總操作次數為調和級數級別，用map維護操作，并每次撤回操作，即可達到時間復雜度O(nlog^2n)，
AC代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
using namespace std;
inline int re_ad()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
int T;
int n,m;
map<int,int> mp;
map<int,int>::iterator it;
int c[100010],a[100010],ans;
int z[2000010],num;
inline int ma(int x,int y){return x>y?x:y;}inline int ab(int x){return x>0?x:-x;}
struct node{int id,num;};
stack<node> cz;
int main()
{
freopen("div.in","r",stdin);
freopen("div.out","w",stdout);
register int i,j;
register int x,y,b;
register node f;
register int fl;bool fla;
T=re_ad();
while(T--)
{
n=re_ad();m=re_ad();mp.clear();ans=0;num=0;
for(i=1;i<=n;++i)
{
c[i]=re_ad();a[i]=re_ad();num+=c[i];
mp[(a[i]+1)%m]+=c[i];mp[(a[i])%m]-=c[i];
}
if(num%m==0)++ans;
z[0]=0;fl=0;
for(it=mp.begin();it!=mp.end();++it)
{
z[++z[0]]=(*it).first;fl=ma(fl,ab((*it).second));
}
if(!fl){puts("-1");continue;}
for(i=fl+1;i>=2;--i)
{
while(z[0])
{
x=z[z[0]--];y=mp[x];b=y/i;
cz.push((node){x,b});mp[(x+1)%m]+=b;mp[x]-=b*i;
if(b!=0)z[++z[0]]=(x+1)%m;
}
fl=mp.begin()->second;fla=true;
if(fl==0||fl==1-i||fl==i-1)
for(it=mp.begin();it!=mp.end();++it)
{
x=(*it).second;if(x!=fl){fla=false;break;}
}
else fla=false;
if(fla)++ans;
while(!cz.empty())
{
f=cz.top();cz.pop();x=f.id;y=f.num;
if(y){mp[(x+1)%m]-=y;mp[x]+=y*i;--z[0];if(!mp[x])mp.erase(x);if(!mp[(x+1)%m])mp.erase((x+1)%m);}
z[++z[0]]=x;
}
}
printf("%d\n",ans);
}
}T3
題目大意：
（
題解做法：
（我才不會說放圖片是因為pdf復制的內容過于難受）
%%%lsz巨佬，給出了一個復雜度O(log2^2n)預處理題解中的m的做法：
把選0看做選左子樹，選1看做選右子樹，做和上面一樣的dp，打出一個比較大的表，觀察左右子樹的轉移點，會發現在一段內左子樹大小遞增而右子樹大小不變，下一段右子樹大小遞增而左子樹大小不變，我們將這些點稱為轉折點，
觀察轉折點的性質，發現每個轉折點來自的左子樹和右子樹的大小也是一個轉折點，并且左右子樹的D的增量相同，于是我們小資料暴力，大資料通過轉移點的合成得到轉移點（其實每個轉移點對應著上面做法中的一個m），注意2^n的特殊情況即可，
對于每組詢問，二分查找離它最近的轉移點，統計即可，
AC代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
inline long long re_ad()
{
long long x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
int T;
int lg[1000010];long long num[1000010],n;
long long dp[1000010],base[70];
queue<long long> z1,z2;
int z1cs[]={14,15,16,18,19},z2cs[]={8,9,11,12,14,15,15,16,18,19};
long long sum[3000],zd[3000],zs[3000],mx=1100000000000000ll;
int cnt,zt;
inline long long query(long long n)
{
int pla=upper_bound(zd+1,zd+zt+1,n)-zd;
return sum[pla-1]+1ll*(n-zd[pla-1])*zs[pla];
}
int main()
{
freopen("dictionary.in","r",stdin);
freopen("dictionary.out","w",stdout);
register int i,j,las=5;
register long long tmp;
n=1000000;
for(i=1;i<=1000000;++i)lg[i]=lg[i>>1]+1,num[i]=num[i-1]+lg[i];
dp[1]=1;las=1;
for(i=2;i<=n;++i)
{
j=1;dp[i]=dp[j]+dp[i-j]+num[i];
for(j=las;j<i;++j)if(num[j]+dp[j]+dp[i-j]+num[i]<=dp[i])
{dp[i]=min(dp[i],num[j]+dp[j]+dp[i-j]+num[i]);las=j;}else if(j-las>5)break;
}
for(i=0;i<5;++i)z1.push(z1cs[i]);for(i=0;i<10;++i)z2.push(z2cs[i]);
base[0]=1;for(i=1;i<=63;++i)base[i]=base[i-1]<<1;
tmp=22;las=5;cnt=22;
while(1)
{
tmp=z1.front()+z2.front();
if(tmp>mx)break;
if(tmp>=base[las]-1)
{
zd[++zt]=base[las]-1;zs[zt]=++cnt;
z1.push(zd[zt]);z2.push(base[las]-1);z2.push(base[las]-1);++las;
}
zd[++zt]=tmp;zs[zt]=++cnt;
z1.push(tmp);z2.push(tmp);z1.pop();z2.pop();
}//cout<<zt<<" "<<zd[zt];
sum[1]=339;
for(i=2;i<=zt;++i)sum[i]=sum[i-1]+1ll*(zd[i]-zd[i-1])*zs[i];
//for(i=1;i<=zt;++i)cout<<zd[i]<<" "<<zs[i]<<endl;
T=re_ad();
while(T--)
{
n=re_ad();
if(n<=500000)printf("%lld\n",dp[n]);
else printf("%lld\n",query(n));
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277423.html
標籤：其他