赛时5题，G题思路对的不知道为啥没过，对辗转相除法还有递推理解太低是这样的。
F，I
队友切的签到，I似乎是简单构造
A
模拟
这题离谱的一个地方就是我用unordered_map会报错所以改map了。
查了一下语法发现是因为没有自定义哈希函数，所以key值不是常规类型的时候必须自定义哈希函数。（当然也要记得重载运算符
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mkp make_pair
#define int long long
#define fir first
#define sec second
#define lowbit(x) (x&(-x))
#define pis pair<int,string>
const int maxn=2e5+10;
vector<pair<int,string> >st;
map<pis,int>id;
unordered_map<string,int>cnt;
unordered_map<string,int>pre;
int lst=0,k=0,f[maxn],t[maxn],a=0x3f3f3f3f3f;
bool cmp(pis x,pis y){
return x.fir>y.fir;
}
void upd(int x,int k){
while(x<maxn){
t[x]+=k;
x+=lowbit(x);
}
return;
}
int que(int x){
int res=0;
while(x>0){
res+=t[x];
x-=lowbit(x);
}
return res;
}
signed main(){
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++){
int tmp;cin>>tmp;a=min(a,tmp);
}
for(int i=1;i<=n;i++){
string s;int x;
cin>>x>>s;
st.push_back(mkp(x,s));
id[mkp(x,s)]=i;
}
int k=0;
sort(st.begin(),st.end(),cmp);
for(auto i:st){
if(lst!=i.fir) k++,lst=i.fir;
int cha=0;
if(cnt[i.sec]==a)if(pre[i.sec]>i.fir)cha=1;
f[id[i]]=que(k-1)+1-cha;
//cout<<que(k-1)<<"mk"<<endl;
if(cnt[i.sec]<a){
cnt[i.sec]++,upd(k,1);
if(cnt[i.sec]==a)pre[i.sec]=i.fir;
}
}
//cout<<k<<endl;
for(int i=1;i<=n;i++)cout<<f[i]<<endl;
return 0;
}
J
又是学到很多。排序问题的一种解法是观察能否解决比较两个相邻元素的子问题。杭电黑洞合并就是交换两个元素没有任何影响的例子，这个题想到这里列个式子就可以解出排序条件了。。（按c/w值排)
赛时因为太蠢所以是看样例猜的
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inc(i,a,b) for(int i(a);i<=b;i++)
#define dec(i,a,b) for(int i(a);i>=b;i--)
const int maxn=1e5+10;
struct Node{
int w,c;
}a[maxn];
int v[maxn];
bool cmp(const Node &x,const Node &y){
double p=x.w*1.0/max(1.0*x.c,0.00001),q=y.w*1.0/(max(1.0*y.c,0.00001));
return p>q;
}
signed main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].w;
cin>>v[i];
cin>>a[i].c;
}
int ans=0,pre=0;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
ans+=v[i];
ans-=(pre*a[i].c);
pre+=a[i].w;
}
cout<<ans<<endl;
return 0;
}
G
唐氏辗转相除法。放江队写的代码，他这个是直接由前一种必败情况推必胜的。
我一开始想的是就是必胜的贡献给答案然后记录必败的往下推（因为我不会递归我写循环的），唉唉
#include<bits/stdc++.h>
const signed mod=998244353;
inline int Read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
int add(int a,int b){
return ((a+=b)>=mod)?a-mod:a;
}
int mul(int x,int y){
return 1ll*x*y%mod;
}
int fpow(int a,int b){
int ans=1;
while(b){
if(b&1) ans=mul(ans,a);
a=mul(a,a);b>>=1;
}
return ans;
}
int f(int x,int y,int p0,int p1){
if(x==0) return 0;
return mul(fpow(p0,y/x),add(1,mod-f(y%x,x,p1,p0)));
}
signed main(){
int T=Read();
while(T--){
int x=Read(),y=Read();
int p0=Read(),p1=Read(),b=Read();
int inv=fpow(p0+p1,mod-2);
p0=mul(p0,inv);p1=mul(p1,inv);
printf("%d\n",f(x,y,p0,p1));
}
return 0;
}
L
概率题。
有一种可能就是这种无限套娃的，就只能自己套自己。可以写出一个左右两侧都含E的式子然后移项推式子就做完了。
这时候队友以为要三分了，但是没有人会三分（因为是一个反比例函数）。但是其实只要同时比较两个数不就知道斜率了，就可以二分
队友一开始以为是递推写了好久。谁记得有什么递推题能给我补一下。。。