最近有幸膜到了贵省的题目，感觉非常难，就来更一发博客骗访问量...
好吧其实真相是看到吉林的缩写感觉非常亲切，于是就来做一下吉林的省选题。感觉PoPoQQQ好神啊...感觉自己如果打了现场的debuff根本打不过啊..
【D1T1】有意义的字符串
记得这是挺经典的题了？总感觉我见过类似的。数据范围中斐波那契数列的部分提示的很明显了..令[tex]f_n=(\frac{b+\sqrt d}{2})^n+(\frac{b-\sqrt d}{2})^n[/tex]，那么类比斐波那契数列通项公式就可以得到有[tex]f_n=bf_{n-1}+\frac{d-b^2}{4}f_{n-2}[/tex]，然后用矩阵来求[tex]f_n[/tex]最后判断一下[tex]n[/tex]的奇偶性就好了。开始初值带错过不了样例去问鏼爷然后就被婊了真开心。然后写的时候傻逼贴了一个中国剩余定理不知道我想干嘛，毕姥爷这个乘2爆long long的模数也是让我写的特别高潮。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct atom{
int x[2][2];
}A,B;
int mo;
long long n,ans[4],key[4]={29,10973,533009,44386129},x,y,b,d,pre;
atom operator * (atom k1,atom k2){
memset(B.x,0x00,sizeof B.x);
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
for (int k=0;k<2;k++) B.x[i][j]=(B.x[i][j]+1ll*k1.x[i][k]*k2.x[k][j])%mo;
return B;
}
int get(int k,long long k2){
mo=k;
memset(A.x,0x00,sizeof A.x);
A.x[0][0]=b%mo; A.x[1][0]=d%mo;
A.x[0][1]=1; k2--;
if (k2==0) return b;
atom k1=A; k2--;
while (k2){
if (k2&1) k1=k1*A; A=A*A; k2>>=1;
}
return (1ll*k1.x[0][0]*(pre%mo)+1ll*k1.x[1][0]*2)%mo;
}
long long quick(long long k1,long long k2,long long mo){
unsigned long long k3=0;
if (k1<0) k1+=mo; if (k2<0) k2+=mo;
unsigned long long a=k1,b=k2;
while (b){
if (b&1) k3=(k3+a)%mo; a=(a+a)%mo; b>>=1;
}
return k3;
}
long long gcd(long long k1,long long k2,long long &x,long long &y){
if (k2==0){x=1; y=0; return k1;}
long long r=gcd(k2,k1%k2,y,x); y-=k1/k2*x; return r;
}
int main(){
scanf("%lld%lld%lld",&b,&d,&n);
pre=(long long)(trunc((b+sqrt(d))/2));
if (n==0){
cout<<1<<endl; return 0;
}
d=(d-b*b)/4;
for (int i=0;i<4;i++) ans[i]=get(key[i],n);
for (int i=1;i<=3;i++){
long long r=gcd(key[i-1],-key[i],x,y);
key[i]=key[i-1]*key[i]/abs(r);
ans[i]=quick(quick(x,((ans[i]-ans[i-1])/r),key[i]),key[i-1],key[i])+ans[i-1];
ans[i]=ans[i]%key[i];
}
if (n%2==0) ans[3]--;
if (ans[3]<0) ans[3]+=key[3];
printf("%lld\n",ans[3]);
return 0;
}
【D1T2】城池攻占
倍增显然？不过似乎有点卡空间的样子我就没有敢写。考场上的话单点10S我估计就自信平衡树了..感觉做了两年TCO之后数据结构姿势水平明显下降啊...满脑子就是句号的分治啊啥的，感觉没有什么救了呢。实际上用可并堆来做就好了，因为以前一直没有写过带标记的可并堆所以就没有往可并堆的方面想，感觉以前对堆的理解实在是太狭隘了，涨姿势了。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct bian{
int next,point;
}b[310000];
struct tree{
int key,l,r,size;
long long w,a,b;
}t[310000];
int p[310000],n,a[310000],m,root[310000],x[310000],num[310000],d[310000],ans[310000],len;
long long v[310000],h[310000];
void add(int k1,int k2){
b[++len]=(bian){p[k1],k2}; p[k1]=len;
}
void chen(int k1,long long k2){
if (k1==0) return; t[k1].w*=k2; t[k1].a*=k2; t[k1].b*=k2;
}
void addin(int k1,long long k2){
if (k1==0) return; t[k1].w+=k2; t[k1].b+=k2;
}
void pushdown(int k){
if (t[k].a!=1){
chen(t[k].l,t[k].a); chen(t[k].r,t[k].a); t[k].a=1;
}
if (t[k].b){
addin(t[k].l,t[k].b); addin(t[k].r,t[k].b); t[k].b=0;
}
}
int merge(int k1,int k2){
if (k1==0||k2==0) return k1+k2;
if (t[k1].w>t[k2].w) swap(k1,k2);
pushdown(k1); t[k1].r=merge(t[k1].r,k2);
t[k1].size=t[t[k1].l].size+t[t[k1].r].size;
if (t[t[k1].l].key<t[t[k1].r].key) swap(t[k1].l,t[k1].r);
t[k1].key=t[t[k1].l].key+1; return k1;
}
void dfs(int k){
for (int i=p[k];i;i=b[i].next){
int j=b[i].point;
d[j]=d[k]+1; dfs(j);
root[k]=merge(root[k],root[j]);
}
while (root[k]&&t[root[k]].w<h[k]){
int k1=root[k]; ans[k1]=d[ans[k1]]-d[k]; num[k]++;
pushdown(root[k]); root[k]=merge(t[root[k]].l,t[root[k]].r);
}
if (a[k]==0) addin(root[k],v[k]); else chen(root[k],v[k]);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%lld",&h[i]);
for (int i=2;i<=n;i++){
int k1; scanf("%d%d%lld",&k1,&a[i],&v[i]); add(k1,i);
}
for (int i=1;i<=m;i++){
int k1; scanf("%lld%d",&t[i].w,&k1); t[i].a=1;
root[k1]=merge(root[k1],i);
ans[i]=k1;
}
dfs(1);
while (root[1]){
int k1=root[1]; ans[k1]=d[ans[k1]]+1;
root[1]=merge(t[root[1]].l,t[root[1]].r);
}
for (int i=1;i<=n;i++) printf("%d\n",num[i]);
for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
}
【D1T3】装备购买
傻逼题..显然是个拟阵，然后高斯消元一下就没了。然后啊就被卡精度了..WA到死。论嘴巴选手的自我修养。后来对着数据调eps才过，以后做这种题应该选几个模搞的..
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
long double x[510][510];
int n,m,a[510];
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
int k1; scanf("%d",&k1); x[i][j]=k1;
}
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
long long ans=0; int now=0;
for (int i=1;i<=m;i++){
int w=1e9,where=0;
for (int j=now+1;j<=n;j++) if (fabs(x[j][i])>1e-6&&a[j]<w){
w=a[j]; where=j;
}
if (where==0) continue;
now++; swap(a[now],a[where]); ans+=w;
for (int j=1;j<=m;j++) swap(x[now][j],x[where][j]);
for (int j=now+1;j<=n;j++){
double k1=x[j][i]/x[now][i];
for (int k=1;k<=m;k++) x[j][k]-=x[now][k]*k1;
}
}
cout<<now<<" "<<ans<<endl;
return 0;
}
【D2T1】骗我呢
开始码了一遍day2三题的题解结果被is-programmer个逗逼网站吃掉了。那我就再简略的写一遍吧。感觉这题是今年JLOI唯一一道有趣的题目，我自己想出了60分做法。就是显然每一行只有[tex]m+1[/tex]种方法，然后按照字典序把这些放法编号，如果第[tex]i[/tex]行放了第[tex]j[/tex]种，那么第[tex]i-1[/tex]行就只能放[tex]j-1[/tex]种以后的方法了。然后就有一种[tex]O(nm)[/tex]的DP方法。至于标算PoPoQQQ已经写得非常详细了，请出门左转CSDN。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int I[3100000],nI[3100000],mo=1e9+7,n,m,lim=3000010,x,y;
int C(int k1,int k2){
if (k1<k2) return 0;
return 1ll*I[k1]*nI[k2]%mo*nI[k1-k2]%mo;
}
void change1(){
swap(x,y); x--; y++;
}
void change2(){
swap(x,y); x+=m+2; y-=m+2;
}
int main(){
scanf("%d%d",&n,&m);
nI[1]=1;
for (int i=2;i<=lim;i++) nI[i]=1ll*(mo-mo/i)*nI[mo%i]%mo; nI[0]=1;
I[0]=1;
for (int i=1;i<=lim;i++){
nI[i]=1ll*nI[i]*nI[i-1]%mo; I[i]=1ll*I[i-1]*i%mo;
}
x=n+m+1; y=n;
int ans=C(x+y,y);
while (x>=0&&y>=0){
change1(); if (x>=0&&y>=0) ans=(ans-C(x+y,y)+mo)%mo;
change2(); if (x>=0&&y>=0) ans=(ans+C(x+y,y))%mo;
}
x=n+m+1; y=n;
while (x>=0&&y>=0){
change2(); if (x>=0&&y>=0) ans=(ans-C(x+y,y)+mo)%mo;
change1(); if (x>=0&&y>=0) ans=(ans+C(x+y,y))%mo;
}
cout<<ans<<endl;
return 0;
}
【D2T2】管道连接
不知道哪个逗逼在群里说斯坦纳树是T的...害的我想了好久的非斯坦纳树做法。先用斯坦纳树DP出关键点集合[tex]U[/tex]联通的最小边权和，然后就知道了使频道集合[tex]V[/tex]的所有关键点联通的最小边权和。最后在外面套一层DP就可以求出答案了。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
struct bian{
int next,point,w;
}b[6100];
int p[1100],len,dp[1100][1<<10],n,m,K,pd[1100],w[11],d[1100],f[1<<10],bo[1100];
queue<int>Q;
void ade(int k1,int k2,int k3){
b[++len]=(bian){p[k1],k2,k3}; p[k1]=len;
}
void add(int k1,int k2,int k3){
ade(k1,k2,k3); ade(k2,k1,k3);
}
void spfa(int now){
for (int i=1;i<=n;i++){
Q.push(i); pd[i]=1;
}
while (!Q.empty()){
int k=Q.front(); Q.pop();
for (int i=p[k];i;i=b[i].next){
int j=b[i].point;
if (dp[k][now]+b[i].w<dp[j][now]){
dp[j][now]=dp[k][now]+b[i].w;
if (pd[j]==0){
pd[j]=1; Q.push(j);
}
}
}
pd[k]=0;
}
}
int main(){
scanf("%d%d%d",&n,&m,&K);
for (;m;m--){
int k1,k2,k3; scanf("%d%d%d",&k1,&k2,&k3); add(k1,k2,k3);
}
memset(dp,0x3f,sizeof dp);
for (int i=1;i<=K;i++){
int k1,k2; scanf("%d%d",&k1,&k2);
bo[k2]=i; w[k1]+=(1<<i-1);
}
for (int now=1;now<(1<<K);now++){
for (int i=1;i<=n;i++){
if (bo[i]&&(1<<bo[i]-1)==now) dp[i][now]=0;
for (int j=(now-1)&now;j;j=(j-1)&now) dp[i][now]=min(dp[i][now],dp[i][j]+dp[i][now-j]);
}
spfa(now);
}
for (int i=1;i<(1<<K);i++){
int k1=0; f[i]=1e9;
for (int j=1;j<=K;j++) if (i&(1<<j-1)) k1|=w[j];
for (int j=1;j<=n;j++) f[i]=min(f[i],dp[j][k1]);
for (int j=(i-1)&i;j;j=(j-1)&i) f[i]=min(f[i],f[j]+f[i-j]);
}
cout<<f[(1<<K)-1]<<endl;
return 0;
}
【D2T3】战争调度
开始想了好久网络流。其实就是一道傻逼的状压DP，难点全在算复杂度..感觉和NOI2015D2T2好像啊。令[tex]dp_{i,j,k}[/tex]表示点[tex]i[/tex]的父亲中负责战争的集合为[tex]j[/tex]子树中有[tex]k[/tex]个人打仗的最优值，然后暴力DP就好了。注意要避免不必要的运算。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
int n,m,lim,A[1<<9][1<<9],B[1<<9][1<<9],two[1<<9],w[10];
vector<int> find(int k1,int k2,int k3){
vector<int>ans;
if (k1>=lim){
ans.push_back(B[k1-lim][lim-k2-1]); ans.push_back(A[k1-lim][k2]);
return ans;
}
vector<int>a,b,c,d;
a=find(k1<<1,k2,k3+1); b=find((k1<<1)+1,k2,k3+1);
c=find(k1<<1,k2+(1<<k3),k3+1); d=find((k1<<1)+1,k2+(1<<k3),k3+1);
int num=a.size()+b.size()-1;
for (int i=0;i<num;i++) ans.push_back(0);
for (int i=0;i<a.size();i++)
for (int j=0;j<b.size();j++) ans[i+j]=max(ans[i+j],a[i]+b[j]);
for (int i=0;i<c.size();i++)
for (int j=0;j<d.size();j++) ans[i+j]=max(ans[i+j],c[i]+d[j]);
return ans;
}
int main(){
scanf("%d%d",&n,&m); lim=(1<<n-1);
for (int i=1;i<n;i++) two[1<<i-1]=i;
for (int i=0;i<lim;i++){
for (int j=1;j<=n-1;j++) scanf("%d",&w[n-j]);
for (int j=1;j<lim;j++){
int k1=j&(-j); A[i][j]=A[i][j-k1]+w[two[k1]];
}
}
for (int i=0;i<lim;i++){
for (int j=1;j<=n-1;j++) scanf("%d",&w[n-j]);
for (int j=1;j<lim;j++){
int k1=j&(-j); B[i][j]=B[i][j-k1]+w[two[k1]];
}
}
vector<int>ans; int num=0; ans=find(1,0,0);
for (int i=0;i<=m;i++) num=max(num,ans[i]);
cout<<num<<endl;
}
评论 (0)
