做网站导流/小江seo
牛客练习赛83
水了一波第三，然而感觉和第一的思维差了很远，补一下第一的思路
A.追求女神
签到题
#include<bits/stdc++.h>
using namespace std;
int t,n,a,b,c,p,q,r;
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);p=q=r=0;bool ok=1;for(int i=1;i<=n;++i){scanf("%d%d%d",&a,&b,&c);int x=a-p,y=abs(q-b)+abs(r-c);if(!(x>=y && (x-y)%2==0)){ok=0;}p=a,q=b,r=c;}puts(ok?"Yes":"No");}return 0;
} B.计算几何（补思路）
统计[l,r]内二进制1为奇数的数的个数
写数位dp纯属是没脑子，
考虑偶数x和x|1一定奇偶性不同，
[0,x]里有(x+1)/2对，然后考虑最后一个数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll l,r;
ll cal(ll x){//[0,x] return (x+1)/2+(x%2==0 && (__builtin_popcount(x)&1));
}
int main(){scanf("%d",&t);while(t--){scanf("%lld%lld",&l,&r);printf("%lld\n",cal(r)-cal(l-1));}return 0;
} C.集合操作（补思路）
n(n<=1e6)个数的可重集合s，一次操作为将s中最大值减去p(0<=p<=1e18)。
小 LLL 想知道，如果给你s,p，以及操作次数 k(0<=k<=1e18)，你能求出最后的集合吗？
注意：你只需要从小到大输出，并保证 x∈s,∣x∣≤LongLongMax。
保证输入的集合每个元素均在[0,1e18]之间
直接二分最大值区间不一定是单调的，
但是可以二分最大值不超过的值是p的哪个倍数，然后剩下的不到n次就暴力模拟，写起来比较复杂
考虑先排序，然后O(n)“削峰”构造答案，削成平均值之后再考虑逐个削
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,i,j;
ll k,p,a[N];
__int128 now;
int main(){scanf("%d%lld%lld",&n,&k,&p);for(i=1;i<=n;++i){scanf("%lld",&a[i]);}sort(a+1,a+n+1);if(!p || !k){for(i=1;i<=n;++i){printf("%lld%c",a[i]," \n"[i==n]);}return 0;}for(i=n;i>1;--i){now+=a[i];if((now-p*k)/(n+1-i)>a[i-1]){break;}}if(i==1)now+=a[1];ll v=(now-p*k)/(n+1-i);for(j=n;j>=i;--j){ll x=(a[j]-v)/p;a[j]-=x*p;k-=x;}sort(a+i,a+n+1);for(j=n;j>=i;--j){if(k){a[j]-=p;k--;}}sort(a+1,a+n+1);for(j=1;j<=n;++j){printf("%lld%c",a[j]," \n"[j==n]);}return 0;
} D.数列递推
经典trick，分值域讨论，数论分块+前缀和+分块
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,K=350,mod=998244353;
int n,f[N],g[N][K];
int main(){scanf("%d",&n);scanf("%d",&f[0]);for(int j=1;j<K;++j){g[0][j]=f[0];}for(int i=1;i<=n;++i){for(int l=1,r,v;l<=i;l=r+1){r=i/(i/l),v=i/l;if(v<K){f[i]=((f[i]+g[i-l*v][v])%mod+(mod-(i-r*v-v<0?0:g[i-r*v-v][v])%mod)%mod)%mod;}else{for(int j=i-l*v;j>=i-r*v;j-=v){f[i]=(f[i]+f[j])%mod;}}}for(int j=1;j<K;++j){g[i][j]=(g[i][j]+f[i])%mod;if(i>=j)g[i][j]=(g[i][j]+g[i-j][j])%mod;}printf("%d",f[i]);if(i!=n)putchar(' ');}return 0;
}E.小L的疑惑(补思路)
小L手中有面值a,b(a,b<=1e9)的金币，两种面值均为正整数且彼此互素。每种金币小 L都有无数个。
在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。
现在小L想知道在无法准确支付的物品中，第k(k<=1e7)贵的价值是多少金币？
根据“小凯的疑惑”，注意到答案一定是a*b-a-b再减去若干个a，减去若干个b，
自己的做法是，像leetcode丑数一样，维护一个双指针，每次要么减a，要么减b
#include<bits/stdc++.h>
using namespace std;
const int K=1e7+10;
typedef long long ll;
ll dp[K],a,b,k;
int main(){int da=1,db=1;scanf("%lld%lld%lld",&a,&b,&k);dp[1]=a*b-a-b;for(int i=2;i<=k;++i){dp[i]=max(dp[da]-a,dp[db]-b);if(dp[i]==dp[da]-a)da++;if(dp[i]==dp[db]-b)db++;}printf("%lld\n",dp[k]);return 0;
}第一名的做法是，考虑m+y*n(x∈Z)和m+(y+1)*n之间有多少个数
m+y*n每大于一次(x+1)*m，就相当于打了一个差分的+1标记，
因为(x+1)*m+n此后会落在[m+y*n,m+(y+1)*n]内，
(x+1)*m+2*n会落在[m+(y+1)*n,m+(y+2)*n]内，以此类推
这样的前提是，不能有两个相同的端点在+n时在同一个值上有贡献，
而这样最小的区间是m+m*n和(n+1)*m+0*n，已经大于了n*m-n*m，所以不会出现冲突
#include<bits/stdc++.h>
using namespace std;
const int K=1e7+10;
typedef long long ll;
const int N=1e4+10;
int a,b,i,j,rk,l,k;
ll x[N],v;
int main(){scanf("%d%d%d",&a,&b,&k);if(a>b)swap(a,b);rk=1,l=1,v=b+a;while(rk<k){rk+=l;//能产生贡献的当前左端点数l,其值为l*b+r*a(r>=1)if(v>1ll*(l+1)*b){l++;rk++;}v+=a;}//形如b+x*a<i*b+q*a<=b+(x+1)*a 其中p<=l 对排名[k,rk]的数起贡献//右半部分可以化成q的不等式 解qfor(i=1;i<=l;++i){x[i]=1ll*(v-1ll*i*b)/a*a+1ll*i*b;}sort(x+1,x+l+1);printf("%lld\n",1ll*a*b-x[l-(rk-k)]);return 0;
}后续：
用这个做法，还能证明>=n*m-n-m的数都能被表示出
设n>m，可以考虑到((m-1)*n-m,(m-1)*n]这个长度为m的区间
对于每个i∈[0,m-2]，由于i*n<(m-1)*n-m，一定存在一个ki，
使得i*n+ki*m落在这个长度为m的区间内，即(m-1)*n-m<i*n+ki*m<=(m-1)*n，
由于ki唯一，用右式解ki即可，
且根据反证法，可证明不存在i1n+k1*m=i2n+k2*m(i1,i2∈[0,m-2])
证毕，后续对每个长度为m的区间归纳证即可