A. 模板题
考场上我没看数据范围，看出来之后甚至妄想找到一个O(1) 的方法?
B. THUSC
最重要的是 ， 考虑实际上影响排名的只有 $ \frac {x}{y}$
事实上我们再确定了一个 $ \frac {x}{y}$ 时，大部分二元组的相对位置已经确定了，不能确定的实际上只有 相等的情况
我们发现 对于一个$ \frac {x}{y}$ ，存在多个相等的情况，但有些的a[i]x+b[i]y是不相等的，也就是，不能互相交换
所以我们可以确定 方案数为 $ \sum p[1]!p[2]!……$
好像只有我打的 hash 判断?
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define N 1005
inline int read(){
int x=0,f=1; char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1; c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^'0'); c=getchar();}
return x*f;
}int a[N],b[N],n,ans,mod=998244353,f[N],base=114514987;
int st[N*N],top,inv[N];
ull hhh(int x,int y,int z){return (ull)(x*base*base+y*base+z);}
ull ha(int x,int y,int val){return (ull)(x*base*base+y*base+val);}
ull hh(int x,int y){return (ull)x*base+y;}
int qpow(int x,int y){
int z=1;
while(y){
if(y&1) z=z*x%mod;
x=x*x%mod;
y>>=1;
}return z;
}
unordered_map< ull ,int> mp;
unordered_map< ull ,int > mul,vis;
int gcd(int a,int b){
if(!b) return a;
return gcd(b,a%b);
}signed main(){
// freopen("date.txt","r",stdin);
n=read();
for(int i=1;i<=n;i++) a[i]=read(),b[i]=read();
f[0]=1;
for(int i=1;i<=n;i++) f[i]=f[i-1]*i%mod;
for(int i=0;i<=n;i++) inv[i]=qpow(f[i],mod-2);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) continue;
if(!((a[i]>a[j])&&(b[i]<b[j]))) continue;
int xx=b[j]-b[i],yy=a[i]-a[j];
int gg=gcd(xx,yy); xx/=gg; yy/=gg;
int vv=a[j]*xx+b[j]*yy;
ull z1=hhh(xx,yy,i),z2=hhh(xx,yy,j);
ull h1=ha(xx,yy,vv),h2=hh(xx,yy);
if(!mul[h2]) {st[++top]=h2;}
int be=mp[h1];
if(!vis[z1]) mp[h1]++;
if(!vis[z2]) mp[h1]++;
vis[z1]=vis[z2]=1;
if(!mul[h2]) mul[h2]=1;
mul[h2]=mul[h2]*(f[mp[h1]])%mod*inv[be]%mod;
}
}for(int i=1;i<=top;i++) ans=(ans+(mul[st[i]]-1))%mod;
cout<<ans+1<<endl;
return 0;
}
C. 8ady
暴力打表或者分析后考虑转化题意 ：
一个前缀最大序列，每个能填的位置为 [1, min(i+m-1,n)-cnt ]，求方案数
发现这玩意增长得非常快，所以询问第 K 大大概只有后30位是不确定的
剩下的都是往上填，考虑每次 \(n^{3}\) 暴力
其实我觉得这题没有那么好打，看别人打的太巧妙了，抠下来
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000005
inline int read(){
int x=0,f=1; char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1; c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^'0'); c=getchar();}
return x*f;
}int b[N],f[N],r[N],w,n,m,k,maxn=0,ans[N];
int check(int a,int x){
int sum=1;
for(int i=x;i<=a-1;i++) {
sum*=(r[i]-i);
if(sum>=k) return k+1;
}for(int i=a+1;i<=w;i++) {
sum*=(r[i]-(i-1));
if(sum>=k) return k+1;
}
return sum;
}
void getsum(int x){
for(int i=x;i<=w;i++){
int sum=check(i,x);
if(sum>=k){
swap(f[i],f[x]); swap(r[i],r[x]);
sort(f+x+1,f+w+1); sort(r+x+1,r+w+1);
return;
}k-=sum;
}
}
void work(){
int sum=0;
for(int i=max((int)1,w-20);i<=w;i++) {
getsum(i);
// cout<<f[i]<<" "<<endl;
}
}
signed main(){
// freopen("date.txt","r",stdin);
// freopen("T1.out","w",stdout);
n=read(); m=read(); k=read();
for(int i=1;i<=n;i++) b[i]=read();
for(int i=1;i<=n;i++){
maxn=max(maxn,b[i]);
if(maxn==b[i]) {
f[++w]=b[i]; r[w]=min(n,i+m-1)-(i-w);
}else ans[i+m-1]=b[i];
}work();
int yg=0;
for(int i=1;i<=n;i++){
if(!ans[i]) ans[i]=f[++yg];
}for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
printf("\n");
return 0;
}
T4
不会