这场爆零了。(惨
先把题目发上来吧。
A. 躲避技能
难度:绿
机房大佬又给出解法:对于每个账号的位置,我们+1;而关键点,我们-1。(这里其实可以不必考虑正负,最后取abs就行了)
然后遍历一遍整棵树,将每个节点(除了根节点)作为根的子树点权和算出来,乘上该节点与其父亲连的边的边权,每个节点的加起来就行了。
仔细想发现这样做是很自然的。不必走的边自然会被省掉,手玩一下就能领会了。
当然这题还有很恶心的高精度。(连签到题都不给吗???)
#include<bits/stdc++.h>
#define ll long long
#define mxn 100010
using namespace std;
ll n,m,len[mxn],q[mxn];
ll val[mxn][110];
ll ans[110],l,sum,lstw;
struct edge{
ll v,id;
};
vector<edge> t[mxn];
int dfs(int u,int f){
int sum=0;
for(int i=0;i<t[u].size();i++){
int v=t[u][i].v;
if(v==f)continue;
ll eid=t[u][i].id;
int a=dfs(v,u);
l=max(len[eid],l*1ll);
for(int j=1;j<=len[eid];j++)
ans[j]=ans[j]+fabs(val[eid][j]*a);
sum+=a;
for(int j=l;j;j--)
ans[j+1]+=ans[j]/100000,ans[j]%=100000;
if(ans[l+1])l++;
}
return sum+q[u];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
// freopen("skill.in","r",stdin);
// freopen("skill.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++){int s;cin>>s;q[s]++;}
for(int i=1;i<=m;i++){int s;cin>>s;q[s]--;}
for(int i=1;i<n;i++){
int u,v;
string w;
cin>>u>>v>>w;
int a=1,b=0;
for(int j=0;j<w.length();j++){
b=b+a*(w[j]-'0'),a*=10;
if((j+1)%5==0)val[i][++len[i]]=b,a=1,b=0;
}
if(w.length()%5!=0)val[i][++len[i]]=b;
t[u].push_back((edge){v,i});
t[v].push_back((edge){u,i});
}
dfs(1,0);
for(int i=l;i;i--){
if(i!=l){
int k=10000;
for(int j=1;j<=5;j++){
cout<<ans[i]/k;
ans[i]-=ans[i]/k*k,k/=10;
}
}
else cout<<ans[i];
}
return 0;
}
B. 奶茶兑换券
难度:绿-蓝
比较考验思维和乱猜结论能力的贪心。
首先,我们要尽可能让买两杯省的钱小于分别买两杯省的钱。因此,\(b_i+b_j\) 必须大于 \(m\)。
然后我们就把比 \(\frac{m}{2}\) 大的数和比 \(\frac{m}{2}\) 小的数分开。尽可能让这两组一一匹配。
发现在小的数这一组中,越大的数越匹配不到,所以让大的优先匹配。
最后让剩下的多的自行匹配就行了,这里怎么匹配答案都是一样的。
#include<bits/stdc++.h>
#define ll long long
#define mxn 100010
#define mp make_pair
#define pll pair<long long,long long>
using namespace std;
ll n,m,ans,sum,l,r,lcnt,rcnt,lsum;
set<pll> tea;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
// freopen("tea.in","r",stdin);
// freopen("tea.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
ll a,b;
cin>>a>>b;
b%=m;
if(b){
b=m-b;
sum+=b*a;
tea.insert(mp(b,a));
}
}
set<pll>::iterator r=tea.lower_bound(mp(m/2,0)),l=r;
l--;
if(r==tea.begin()){
lsum=0;
while(r!=tea.end()){
lsum+=(*r).second;
r++;
}
cout<<sum-lsum/2*m;
return 0;
}
lcnt=(*l).second,rcnt=(*r).second;
if((*r).first==m/2){
r++,rcnt=0;
if(r!=tea.end())rcnt=(*r).second;
}
while(1){
if(!rcnt){if(r==tea.end())break;r++,rcnt=(*r).second;}
if(!lcnt){if(l==tea.begin())break;l--,lcnt=(*l).second;}
while((*l).first+(*r).first<m&&r!=tea.end()){r++;rcnt=(*r).second;}
if(r==tea.end())break;
ll cnt=min(lcnt,rcnt);
lcnt-=cnt,rcnt-=cnt,ans+=cnt;
sum-=cnt*m;
}
lsum=0;
r=tea.lower_bound(mp(m/2,0));
while(r!=tea.end()){
lsum+=(*r).second;
r++;
rcnt=(*r).second;
}
cout<<sum-(lsum-ans)/2*m;
return 0;
}
C. 帮助
难度:蓝
题目看起来好绕啊qwq
机房巨佬说这题扫描线秒了,可我连扫描线是什么也不知道啊(我好菜啊~~
设 \(g_{i,j}\) 为所有成绩为 \(j\) 且愿意帮助成绩为 \(i\) 的人做题数之和。
于是有递推式:
\(g_{i,j}=g_{i-1,j}+\sum\limits_{c_p=i,t_p=j}f_p-\sum\limits_{d_p=i-1,t_p=j}f_p\)
用树状数组维护,注意离散化。
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
#define pll pair<ll,ll>
#define mxn 100010
using namespace std;
ll n,f[mxn],t[mxn];
ll a[mxn],b[mxn],c[mxn],d[mxn];
ll num[mxn],id1[mxn],id2[mxn];
ll tre[mxn],ans[mxn],l,noww;
ll sort_by_t[mxn],sort_by_c[mxn];
priority_queue<pll,vector<pll>,greater<pll> > q;
ll lowbit(ll x){
return x&(-x);
}
ll ask(ll x){
ll ret=0;
while(x){
ret+=tre[x];
x-=lowbit(x);
}
return ret;
}
void treadd(ll x,ll val){
while(x<=l){
tre[x]+=val;
x+=lowbit(x);
}
return;
}
bool cmpt(int a,int b){
return num[a]<num[b];
}
bool cmpc(int a,int b){
return c[a]<c[b];
}
void lisan(){
sort(t+1,t+n+1);
l=unique(t+1,t+n+1)-t-1;
for(int i=1;i<=n;i++){
ll aa,bb,cc,dd;
cin>>aa>>bb>>cc>>dd;
num[i]=lower_bound(t+1,t+l+1,num[i])-t;//离散化!
a[i]=lower_bound(t+1,t+l+1,aa)-t;
b[i]=upper_bound(t+1,t+l+1,bb)-t-1;
c[i]=lower_bound(t+1,t+l+1,cc)-t;
d[i]=upper_bound(t+1,t+l+1,dd)-t-1;
}
sort(sort_by_c+1,sort_by_c+n+1,cmpc);//按帮助别人的范围排序c
sort(sort_by_t+1,sort_by_t+n+1,cmpt);//按成绩排序t
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
// freopen("help.in","r",stdin);
// freopen("help.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)cin>>f[i];
for(int i=1;i<=n;i++){
sort_by_c[i]=sort_by_t[i]=i;
cin>>t[i];
num[i]=t[i];
}
lisan();
for(int i=1;i<=n;i++){//按成绩排序遍历
while(c[sort_by_c[noww]]<=num[sort_by_t[i]]&&noww<=n){//看i能被多少人帮助
if(d[sort_by_c[noww]]>=num[sort_by_t[i]]){
q.push(mp(d[sort_by_c[noww]],sort_by_c[noww]));
treadd(num[sort_by_c[noww]],f[sort_by_c[noww]]);
}
noww++;
}
while(q.size()&&q.top().first<num[sort_by_t[i]]){
treadd(num[q.top().second],-f[q.top().second]);
q.pop();//再把不能的去掉
}
ans[sort_by_t[i]]+=ask(b[sort_by_t[i]])-ask(a[sort_by_t[i]]-1);//在受帮助的范围里减去
if(num[i]<c[i]||num[i]>d[i]||num[i]<a[i]||num[i]>b[i])ans[i]+=f[i];//加上他自己做的
}
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
return 0;
}
D. 神奇的变换
难度:紫-黑
恶心数学题,出出来就是为了恶心别人的。
不想改了,就这样吧。
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define mxn 100001
#define mxm 350
using namespace std;
int pp[200][mxn],pre[80001][mxm],mipri[mxn*10],mapri[mxn];
int pri[mxn],wh[mxn*10],vis[mxn],fir[mxn];
int k[mxn+1],l[mxm],r[mxm];
int type,n,m,sq;
ll kk[mxm][mxm],inv[mxn],vv[mxn],ans;
bool is[mxn*10];
vector<int> a[mxn];
vector<ll> b[mxn],e[mxn];
inline ll qow(ll a,int b){
ll ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
inline void init_pri(){
n=1000000;
for(int i=2;i<=n;i++){
if(!is[i]) pri[wh[i]=++pri[0]]=i,fir[wh[i]]=100001,mipri[i]=wh[i];
for(int j=1;j<=pri[0]&&i*pri[j]<=n;j++){
is[i*pri[j]]=1;
mipri[i*pri[j]]=j;
if(i%pri[j]==0) break;
}
}
}
inline void read_all(){
cin>>n>>m>>type;
for(int i=1;i<=n;i++){
int val;
cin>>val;
while(val!=1&&is[val])a[i].push_back(mipri[val]),val/=pri[mipri[val]];
if(val!=1){
a[i].push_back(wh[val]);
if(val>1000) mapri[i]=wh[val];
}
}
}
inline void init_sq(){
for(;(sq+1)*(sq+1)<=n;sq++);
k[100001]=n;
for(int i=1;i<=n;i++){
k[i]=(i+sq-1)/sq;
if(!l[k[i]]) l[k[i]]=i;
r[k[i]]=i;
for(int j:a[i]){
pre[j][k[i]]++;
if(pri[j]<=1000) pp[j][i]++;
if(fir[j]>i) fir[j]=i;
}
}
for(int i=1;i<=pri[0];i++) for(int j=k[fir[i]]+1;j<=k[n];j++)
pre[i][j]+=pre[i][j-1];
for(int i=1;pri[i]<=1000;i++) for(int j=fir[i]+1;j<=n;j++) pp[i][j]+=pp[i][j-1];
}
inline void init_pow(){
for(int i=1;i<=n;i++) inv[i]=qow(i,mod-2),vv[i]=inv[i-1]*i%mod;
if(type-3)return;
for(int i=1;i<=pri[0];i++){
if(pri[i]<=1000){
ll now=1;
b[i].resize(pre[i][k[n]]+1);
b[i][0]=1;
for(int j=1;j<=pre[i][k[n]];j++){
now=(now*pri[i]+1)%mod;
b[i][j]=now;
}
}
else{
ll now=1;
b[i].resize(pre[i][k[n]]+1);
e[i].resize(pre[i][k[n]]+1);
b[i][0]=e[i][0]=1;
for(int j=1;j<=pre[i][k[n]];j++){
e[i][j]=pri[i]+qow(now,mod-2);
now=(now*pri[i]+1)%mod;
b[i][j]=now;
}
}
}
}
inline void init_kans(){
int sz=pri[0]*4+4;
if(type==1){
for(int i=1;i<=k[n];i++){
ll ans1=1;
for(int j=i;j<=k[n];j++){
for(int p=l[j];p<=r[j];p++)
if(mapri[p]){
int &cnt=++vis[mapri[p]];
ans1*=-1;if(cnt>=2) ans1=0;
}
kk[i][j]=(ans1+mod)%mod;
}
memset(vis,0,sz);
}
}
else if(type==2){
for(int i=1;i<=k[n];i++){
ll ans2=1;
for(int j=i;j<=k[n];j++){
for(int p=l[j];p<=r[j];p++) if(mapri[p]){
int &cnt=++vis[mapri[p]];
ans2=ans2*vv[cnt+1]%mod;
}
kk[i][j]=ans2;
}
memset(vis,0,sz);
}
}
else{
for(int i=1;i<=k[n];i++){
ll ans3=1;
for(int j=i;j<=k[n];j++){
for(int p=l[j];p<=r[j];p++)
if(mapri[p]){
int &cnt=++vis[mapri[p]],&num=mapri[p];
ans3=ans3*e[num][cnt]%mod;
}
kk[i][j]=ans3;
}
memset(vis,0,sz);
}
}
}
inline void query(int l,int r){
if(k[l]==k[r]){
if(type==1){
ans=1;
for(int i=1;pri[i]<=1000;i++){
int cnt=pp[i][r]-pp[i][l-1];
if(cnt==1) ans*=-1;
else if(cnt>=2) ans=0;
}
for(int i=l;i<=r;i++)
if(mapri[i]){
int &num=mapri[i],&cnt=++vis[num];
if(cnt==1) ans*=-1;
else ans=0;
}
for(int i=l;i<=r;i++)
if(mapri[i])
vis[mapri[i]]--;
ans=(ans+mod)%mod;
cout<<ans<<'\n';
}
else if(type==2){
ans=1;
for(int i=1;pri[i]<=1000;i++){
int cnt=pp[i][r]-pp[i][l-1];
(ans*=(cnt+1))%=mod;
}
for(int i=l;i<=r;i++) if(mapri[i]){
int &num=mapri[i],&cnt=++vis[num];
(ans*=vv[cnt+1])%=mod;
}
for(int i=l;i<=r;i++) if(mapri[i]) vis[mapri[i]]--;
cout<<ans<<'\n';
}
else{
ans=1;
for(int i=1;pri[i]<=1000;i++){
int cnt=pp[i][r]-pp[i][l-1];
(ans*=b[i][cnt])%=mod;
}
for(int i=l;i<=r;i++)
if(mapri[i]){
int &num=mapri[i],&cnt=++vis[num];
(ans*=e[num][cnt])%=mod;
}
for(int i=l;i<=r;i++)
if(mapri[i])
vis[mapri[i]]--;
cout<<ans<<'\n';
}
return;
}
if(type==1){
ans=1;
if(k[l]+1<=k[r]-1) ans=kk[k[l]+1][k[r]-1];
for(int i=1;pri[i]<=1000;i++){
int cnt=pp[i][r]-pp[i][l-1];
if(cnt==1) ans*=-1;
else if(cnt>=2) ans=0;
}
for(int i=l;k[i]==k[l];i++)
if(mapri[i]){
int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
if(cnt==1) ans*=-1;
else if(cnt>=2) ans=0;
}
for(int i=r;k[i]==k[r];i--)
if(mapri[i]){
int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
if(cnt==1) ans*=-1;
else if(cnt>=2) ans=0;
}
for(int i=l;k[i]==k[l];i++)if(mapri[i])vis[mapri[i]]--;
for(int i=r;k[i]==k[r];i--)if(mapri[i])vis[mapri[i]]--;
(ans+=mod)%=mod;
cout<<ans<<'\n';
}
else if(type==2){
ans=1;
if(k[l]+1<=k[r]-1) ans=kk[k[l]+1][k[r]-1];
for(int i=1;pri[i]<=1000;i++){
int cnt=pp[i][r]-pp[i][l-1];
(ans*=(cnt+1))%=mod;
}
for(int i=l;k[i]==k[l];i++)
if(mapri[i]){
int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
(ans*=vv[cnt+1])%=mod;
}
for(int i=r;k[i]==k[r];i--)
if(mapri[i]){
int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
(ans*=vv[cnt+1])%=mod;
}
for(int i=l;k[i]==k[l];i++) if(mapri[i]) vis[mapri[i]]--;
for(int i=r;k[i]==k[r];i--) if(mapri[i]) vis[mapri[i]]--;
cout<<ans<<'\n';
}
else{
ans=1;
if(k[l]+1<=k[r]-1) ans=kk[k[l]+1][k[r]-1];
for(int i=1;pri[i]<=1000;i++){
int cnt=pp[i][r]-pp[i][l-1];
(ans*=b[i][cnt])%=mod;
}
for(int i=l;k[i]==k[l];i++)
if(mapri[i]){
int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
(ans*=e[num][cnt])%=mod;
}
for(int i=r;k[i]==k[r];i--)
if(mapri[i]){
int &num=mapri[i],cnt=++vis[num]+(pre[num][k[r]-1]-pre[num][k[l]]);
(ans*=e[num][cnt])%=mod;
}
for(int i=l;k[i]==k[l];i++) if(mapri[i]) vis[mapri[i]]--;
for(int i=r;k[i]==k[r];i--) if(mapri[i]) vis[mapri[i]]--;
cout<<ans<<'\n';
}
}
inline void query(){
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
l^=ans,r^=ans;
query(l,r);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
// freopen("change.in","r",stdin);
// freopen("change.out","w",stdout);
init_pri();
read_all();
init_sq();
init_pow();
init_kans();
query();
return 0;
}
标签:20241002,int,ll,mxn,num,ans,模拟,define
From: https://www.cnblogs.com/nagato--yuki/p/18444560