【D NKOJ-P10088】宝石转换 100pts

考试思路

递归解题,以下公式中的a[A−n]a[A-n]a[A−n]表示aaa颗nnn级红宝石，b[B−n]b[B-n]b[B−n]，表示bbb颗nnn级蓝宝石；

∵a[A−n]⟺a[A−(n−1)]+ax[B−n]∵ax[B−n]⟺ax[A−(n−1)]+axy[B−(n−1)]∵b[B−n]⟺b[A−(n−1)]+by[B−(n−1)]\because a[A-n]\Longleftrightarrow a[A-(n-1)]+ax[B-n] \\\because ax[B-n]\Longleftrightarrow ax[A-(n-1)]+axy[B-(n-1)]\\\because b[B-n]\Longleftrightarrow b[A-(n-1)]+by[B-(n-1)]∵a[A−n]⟺a[A−(n−1)]+ax[B−n]∵ax[B−n]⟺ax[A−(n−1)]+axy[B−(n−1)]∵b[B−n]⟺b[A−(n−1)]+by[B−(n−1)]

∴a[A−n]+b[B−n]⟺(a+ax+b)[A−(n−1)]+(axy+by)[B−(n−1)]\therefore a[A-n]+b[B-n] \Longleftrightarrow (a+ax+b)[A-(n-1)]+(axy+by)[B-(n-1)]∴a[A−n]+b[B−n]⟺(a+ax+b)[A−(n−1)]+(axy+by)[B−(n−1)]

以上即为推论:

Ac Code

#include
#pragma GCC optimize(2)
#define int long long
using namespace std;
int n,x,y;
int dfs(int h,int l,int a,int b){//a,b为个数，h，l为等级，按照上述结论递推(各位dalao可以用效率更高的循环代替这个)if(h<=1||l<=1){return b;}return dfs(h-1,l-1,a*(x+1)+b,a*x*y+b*y);
}
signed main(){scanf("%lld%lld%lld",&n,&x,&y);printf("%lld",dfs(n,n,1,0));return 0;
}

【E NKOJ-P10090】ljj的距离 70pts

考场思路

这题很明显，不能暴力枚举，但是我们可以发现通过求s,ts,ts,t长度的lcm再取倍数就可以优化时间复杂度；即lcm优化（自己取的）

正解

首先，lcm优化的思路没有问题，我们可以把答案表示为,其中ddd为公倍数区间中s,ts,ts,t之间的距离：
slong×nlcm(slong,tlong)×d\frac{s_{long} \times n}{\mathrm{lcm}(s_{long},t_{long})}\times dlcm(slong​,tlong​)slong​×n​×d

我们发现，我们只能优化如何求出ddd的值；不妨逆着思考——ddd是si≠tis_i \ne t_isi​=ti​的个数，很明显，我们求出si=tis_i = t_isi​=ti​的个数更容易且可以·求出ttt值，记其为 d1d_1d1​；

• 当一个sis_isi​和tjt_jtj​在反转后正好可以重叠，那应当有：(x,yx,yx,y是反转多少次后他们重叠，是一个未知变量)
  i+x×slong=j+y×tlongi+x \times s_{long}=j+y \times t_{long}i+x×slong​=j+y×tlong​

• 化简，即两边同时对gcd⁡(slong,tlong)\gcd(s_{long},t_{long})gcd(slong​,tlong​)取模,可得：

i≡jmodgcd⁡(slong,tlong)i \equiv j \mod\gcd(s_{long},t_{long})i≡jmodgcd(slong​,tlong​)

一下子思路就很清晰了：我们只需要用一个数组number[i][j]表示对在字符串sss当中gcd⁡(slong,tlong)\gcd(s_{long},t_{long})gcd(slong​,tlong​)取模值为iii的编号为jjj的字母；接着遍历一遍ttt,看一下哪些字母满足条件，遍历到一个把计数器加一，最后把计数器按照上述变形逆推回去，带入表达式中求解即可；

Ac Code

#include
#define int long long
using namespace std;
int n,m,x,y;
int ans,gcds,lcms;
int number[1000005][30];
string sx,sy;
int get(char num){return num-'a'+1;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;
}
signed main(){scanf("%lld%lld",&n,&m);cin>>sx>>sy;x=sx.size();y=sy.size();gcds=gcd(max(x,y),min(x,y));lcms=x*y/gcds;for(int i=0;inumber[(i+1)%gcds][get(sx[i])]++;}for(int i=0;ians+=number[(i+1)%gcds][get(sy[i])];}ans=(lcms-ans)*(n*x/lcms);printf("%lld",ans);return 0;
}

【F NKOJ-P10087】零它走了 44pts

考场思路

爆搜！记忆化爆搜！TLE爆搜！
很明显，4s的时限也救不了我的记忆化深搜；

正解

先给大家来一张图理解一下：

因为我们要求的是图中sss的最小值，所以我们一次枚举每一座“B桥”的情况；

• 对于第iii座“B桥”，是经过这座桥路径最短的“A桥”“C桥”的坐标一定是在所有“AC桥中”最靠近这座桥坐标的那一座，所以我们只需要选择对于当前B桥，应当选择左或是右边的“AC桥”即可；
• 对于选择“AC桥”也有优化，我们先对每一组桥的坐标进行排序，然后发现：当前B桥左边的最近桥肯定在上一座B桥最近桥的右边或是就是上一座B桥最近桥，于是我们只需要提前存储上一个最近桥的编号，从那里开始枚举，知道这个桥的坐标在当前“B桥”的左边或本身；

以上即为思路，实现的时候还是有很多细节，建议诸位自己画个图模拟一下样例；

Ac Code

#include
#define int long long
using namespace std;
const int maxnum=10000000000;
int t,a,b,c;
int da[100005],db[100005],dc[100005];
int mina,minb,minc,minnum;
int nexta,nextc;
signed main(){scanf("%lld",&t);while(t--){scanf("%lld%lld%lld",&a,&b,&c);minnum=maxnum;nexta=nextc=1;for(int i=1;i<=a;i++){scanf("%lld",&da[i]);}for(int i=1;i<=b;i++){scanf("%lld",&db[i]);}for(int i=1;i<=c;i++){scanf("%lld",&dc[i]);}sort(da+1,da+a+1);sort(db+1,db+b+1);sort(dc+1,dc+c+1); for(int i=1;i<=b;i++){int time_min=maxnum,drta,drtc;for(int j=nexta;j<=a;j++){if(time_min>abs(db[i]-da[j])){time_min=abs(db[i]-da[j]);drta=j;}if(da[j]>=db[i]||j==a){nexta=drta;break;}}time_min=maxnum;for(int j=nextc;j<=c;j++){if(time_min>abs(db[i]-dc[j])){time_min=abs(db[i]-dc[j]);drtc=j;}if(dc[j]>=db[i]||j==c){nextc=drtc;break;}}int longs=abs(db[i]-da[drta])+abs(db[i]-dc[drtc]);if(minnum>longs){minnum=longs;mina=drta;minb=i;minc=drtc;}}printf("%lld %lld %lld\n",da[mina],db[minb],dc[minc]);}return 0;
}

完结撒花-彩蛋

• ps:这场比赛让蒟蒻有了NK彩名
• ps:蒟蒻的第一篇游记，以后的游记都会归档在“其他特辑”当中，欢迎各位dalao批评
• ps:最近期末考试刚刚完，所以咕了这么久才发文