背景
T1出了大鍋導致unrated了……
最后排名在70左右，如果不算橙名及以上的那些，那就排到第10左右了，小號錯失一波上分的好機會QAQ……
A
算一下需要的總木棍數，然后就能算出交易次數，要注意精度問題，需要用long double，
代碼如下：
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 300010
#define ll long long
int T,n,m,k;
int main()
{
scanf("%d",&T);while(T--)
{
scanf("%d %d %d",&n,&m,&k);
ll ans=1ll*m*k+1ll*k;
long double p=(long double)(ans-1)/(long double)(n-1);
printf("%lld\n",(ll)ceil(p)+k);
}
}
B
顯然把能動的那些從大到小排序，大的盡量堆在前面，這樣可以使每個前綴都盡可能的大，
代碼如下：
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 300010
#define ll long long
int T,n,a[maxn],l[maxn];
vector<int> b;
bool cmp(int x,int y){return x>y;}
int main()
{
scanf("%d",&T);while(T--)
{
scanf("%d",&n);b.clear();
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
scanf("%d",&l[i]);
if(!l[i])b.push_back(a[i]);
}
sort(b.begin(),b.end(),cmp);
int st=0;
for(int i=1;i<=n;i++){
if(!l[i])a[i]=b[st++];
printf("%d ",a[i]);
}
printf("\n");
}
}
C
dp一下即可，令 f [ i ] [ 0 / 1 ] f[i][0/1] f[i][0/1] 表示干掉了前 i i i 個 boss \text{boss} boss，此時是誰操作，
代碼如下：
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 300010
#define ll long long
int T,n,a[maxn],f[maxn][2];//0表示我操作，1表示朋友操作
int main()
{
scanf("%d",&T);while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i][0]=f[i][1]=1e9;
f[0][0]=0;f[0][1]=1e9;
f[1][1]=a[1];
for(int i=2;i<=n;i++){
f[i][0]=min(f[i-1][1],f[i-2][1]);
f[i][1]=min(f[i-1][0]+a[i],f[i-2][0]+a[i]+a[i-1]);
}
printf("%d\n",min(f[n][0],f[n][1]));
}
}
D
顯然最后保留相鄰的最遠的一對垃圾堆，其他垃圾都要堆過來，用 s e t set set 啥的維護一下就好了，
代碼如下;
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
#define maxn 300010
#define ll long long
#define it set<int>::iterator
#define it2 map<int,int>::iterator
int T,n,q;
set<int> s;//維護所有垃圾
map<int,int> ans;//維護相鄰垃圾的坐標差
void add(int x){ans[x]++;}
void del(int x){ans[x]--;if(!ans[x])ans.erase(x);}
void getans(){
if(s.size()<=2)printf("0\n");
else{
it p=s.end(),p1=s.begin();
it2 p2=ans.end();p--;p2--;
printf("%d\n",*p-*p1-p2->first);
}
}
int main()
{
// scanf("%d",&T);while(T--)
{
scanf("%d %d",&n,&q);s.clear();ans.clear();
for(int i=1,x;i<=n;i++)scanf("%d",&x),s.insert(x);
int last=0;for(int i:s){
if(last)ans[i-last]++;
last=i;
}
getans();
for(int i=1;i<=q;i++){
int id,x;
scanf("%d %d",&id,&x);
if(id==0){
it p=s.lower_bound(x),p1=p;
bool v=false,v1=false;
if(p!=s.begin())p--,del(x-*p),v=true;
if(p1!=s.end())p1++,del(*p1-x),v1=true;
if(v&&v1)add(*p1-*p);
s.erase(x);
}else{
s.insert(x);
it p=s.lower_bound(x),p1=p;
bool v=false,v1=false;
if(p!=s.begin())p--,add(x-*p),v=true;
if(p1!=s.end())p1++,add(*p1-x),v1=true;
if(v&&v1)del(*p1-*p);
}
getans();
}
}
}
E
對于每個盾牌，怪物分成兩類：攻擊力大于等于其防御值的，攻擊力小于其防御值的，
令 a a a 為第一類怪物數量， b b b 為第二類怪物數量，盾牌耐久為 p p p，
考慮一只第一類怪物能造成傷害的情況數，如果
a
≤
p
a\leq p
a≤p 則為
0
0
0，否則為：
C
a
+
b
a
C
a
?
1
p
p
!
b
!
(
a
?
p
)
!
C_{a+b}^a C_{a-1}^p p! b! (a-p)!
Ca+ba?Ca?1p?p!b!(a?p)!
C a + b a C_{a+b}^a Ca+ba? 是在序列中給兩類怪物分配位置， C a ? 1 p C_{a-1}^p Ca?1p? 是從除了自己以外的第一類怪物中找 p p p 個放在自己前面，這樣自己才能造成傷害，剩下的階乘就是表示不在乎相對位置的怪物隨便排列，
考慮一只第二類怪物能造成傷害的情況數，如果
a
<
p
a<p
a<p 則為
0
0
0，否則為：
C
a
+
b
b
?
1
(
b
?
1
)
!
a
!
(
a
?
p
+
1
)
C_{a+b}^{b-1}(b-1)!a!(a-p+1)
Ca+bb?1?(b?1)!a!(a?p+1)
C a + b b ? 1 C_{a+b}^{b-1} Ca+bb?1? 表示給除了自己以外的第二類怪物分配位置，而自己前面一定要有至少 p p p 個第一類怪物，所以剩下的 a + 1 a+1 a+1 個位置里面只有 a + 1 ? p a+1-p a+1?p 個位置能放，然后階乘依然表示不在乎相對順序的怪物隨便放，
注意上面求出來的是方案數，要乘上傷害再除以總方案數才是期望造成的傷害，
代碼如下：
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
#define maxn 300010
#define mod 998244353
int n,m,d[maxn];
struct node{int x,y,pos;}a[maxn];
bool cmp(node x,node y){return x.y<y.y;}
int fac[maxn],inv[maxn],inv_fac[maxn];
void work(){
fac[0]=inv_fac[0]=inv[1]=1;
for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
for(int i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=n;i++)inv_fac[i]=1ll*inv_fac[i-1]*inv[i]%mod;
}
int C(int x,int y){return 1ll*fac[x]*inv_fac[y]%mod*inv_fac[x-y]%mod;}
int sum1=0,sum2=0,ans,Ans[maxn];
int main()
{
scanf("%d %d",&n,&m);work();
for(int i=1;i<=n;i++)scanf("%d",&d[i]),sum1=(sum1+d[i])%mod;
sort(d+1,d+n+1);
for(int i=1;i<=m;i++)scanf("%d %d",&a[i].x,&a[i].y),a[i].pos=i;
sort(a+1,a+m+1,cmp);
int now=0;
for(int i=1;i<=m;i++){
while(d[now+1]<a[i].y)now++,sum2=(sum2+d[now])%mod;
ans=0;
if(a[i].x<=n-now)ans=(ans+1ll*C(n,now-1)*fac[now-1]%mod*fac[n-now]%mod*(n-now-a[i].x+1)%mod*sum2%mod)%mod;
if(a[i].x<n-now)ans=(ans+1ll*C(n,now)*C(n-now-1,a[i].x)%mod*fac[a[i].x]%mod*fac[n-now-a[i].x]%mod*fac[now]%mod*(sum1-sum2+mod)%mod)%mod;
Ans[a[i].pos]=1ll*ans*inv_fac[n]%mod;
}
for(int i=1;i<=m;i++)printf("%d\n",Ans[i]);
}
F
要滿足 x 1 y 1 = x 2 y 2 x_1y_1=x_2y_2 x1?y1?=x2?y2?，相當于 x 2 x 1 = y 1 y 2 = a b \dfrac {x_2} {x_1}=\dfrac {y_1} {y_2}=\dfrac a b x1?x2??=y2?y1??=ba?， a , b a,b a,b 是設出來的一個東西，并且滿足 a > b a>b a>b，
還要滿足 l ≤ x 1 y 1 ≤ r l\leq x_1y_1\leq r l≤x1?y1?≤r，即 ? l x 1 ? ≤ y 1 ≤ ? r x 1 ? \lceil \dfrac l {x_1} \rceil \leq y_1\leq \lfloor \dfrac r {x_1} \rfloor ?x1?l??≤y1?≤?x1?r??，隨著 x 1 x_1 x1? 的減小這個區間的左右端點都會變大，上限是 m m m，記這個區間為 [ L , R ] [L,R] [L,R]，
先列舉 x 1 x_1 x1?，然后考慮列舉 x 1 x_1 x1? 的一個因子 b b b，問題變成：找到一個 y 1 ∈ [ L , R ] y_1\in[L,R] y1?∈[L,R]，并且擁有一個大于 b b b 的因子 a a a，并且 x 2 = x 1 a b ≤ n x_2=x_1\dfrac a b\leq n x2?=x1?ba?≤n，假如我們把 [ L , R ] [L,R] [L,R] 內的所有數的所有因子放到權值線段樹里面，那么就是要找到大于 b b b 的一個最小的 a a a，然后找到這個 a a a 對應的 y 1 y_1 y1?，有了 x 1 , y 1 , a , b x_1,y_1,a,b x1?,y1?,a,b，就可以求出 x 2 , y 2 x_2,y_2 x2?,y2?，最后判一下 x 2 x_2 x2? 是否小于等于 n n n，如果是就找到一組可行解了，
[ 1 , n ] [1,n] [1,n] 的總因子數為 n ln ? n n\ln n nlnn，所以總復雜度大約就是 n log ? 2 n n\log^2 n nlog2n，（雖然題解也是這個復雜度并且也用到了線段樹，但是蒟蒻并沒有看懂題解在說什么，這個做法是蒟蒻瞎yy的qwq……）
代碼如下：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define maxn 200010
#define ll long long
int n,m;
ll L,R;
vector<int> fac[maxn];
void work(){
for(int i=1;i<=maxn-10;i++){
for(int j=i;j<=maxn-10;j+=i)
fac[j].push_back(i);
}
}
struct par{int x,y;};
#define zuo ch[0]
#define you ch[1]
struct node{
int l,r,mid,c,num;node *ch[2];
node(int x,int y):l(x),r(y),mid(l+r>>1),c(0){
if(x<y){
zuo=new node(l,mid);
you=new node(mid+1,r);
}else zuo=you=NULL;
}
void change(int x,int y,int z){
c+=y;if(l==r){if(y==1)num=z;return;}
ch[x>=mid+1]->change(x,y,z);
}
int getsum(int x,int y){
if(l==x&&r==y)return c;
if(y<=mid)return zuo->getsum(x,y);
else if(x>=mid+1)return you->getsum(x,y);
else return zuo->getsum(x,mid)+you->getsum(mid+1,y);
}
par ask(int x){//找到大于等于x的最小的a
if(!c)return (par){0,0};
if(l==r)return (par){l,num};
if(x<=mid&&zuo->getsum(x,mid))return zuo->ask(x);
return you->ask(max(mid+1,x));
}
}*root=NULL;
struct ANS{int x_1,y_1,x_2,y_2;}ans[maxn];
int main()
{
scanf("%d %d %lld %lld",&n,&m,&L,&R);work();
int l=1,r=0;root=new node(1,m);
for(int x_1=n;x_1>=1;x_1--){
ll lto=(ll)ceil(1.0*L/x_1),rto=(ll)floor(1.0*R/x_1);
while(r<m&&r<rto){
for(int i:fac[r+1])root->change(i,1,r+1);
r++;
}
while(l<=m&&l<lto){
for(int i:fac[l])root->change(i,-1,l);
l++;
}
ans[x_1].x_1=-1;
for(int b:fac[x_1])if(b+1<=m){//注意這里，a要大于b但不能大于m
par p=root->ask(b+1);//這里的+1將“找到大于的”變成了“找到大于等于的”
if(!p.x)continue;
int a=p.x,y_1=p.y,x_2=1ll*a*x_1/b,y_2=1ll*y_1*b/a;
if(1ll*a*x_1/b<=n){ans[x_1]=(ANS){x_1,y_1,x_2,y_2};break;}
}
}
for(int i=1;i<=n;i++)if(ans[i].x_1==-1)printf("-1\n");
else printf("%d %d %d %d\n",ans[i].x_1,ans[i].y_1,ans[i].x_2,ans[i].y_2);
}
G
考慮維護一個 o c c [ i ] occ[i] occ[i] 表示當前前綴中數字 i i i 的出現次數模 3 3 3 的值，如果一個區間 [ l , r ] [l,r] [l,r] 是合法的，那么 1 1 1 ~ l ? 1 l-1 l?1 這個前綴的 o c c occ occ 陣列和 1 1 1 ~ r r r 這個前綴的 o c c occ occ 陣列肯定一樣，這個可以用哈希來判斷，
但是對于一個 r r r，并不是所有的擁有相同 o c c occ occ 的 l ? 1 l-1 l?1 都合法，有些數可能出現了 6 6 6 次或以上，這個可以通過維護一個左端點 s t st st 來解決， s t st st 表示 l ? 1 l-1 l?1 最左能取到什么位置，再往左取就會有某個數出現超過 3 3 3 次，然后每次 s t st st 右移的時候把原位置的 h a s h hash hash 值刪掉即可，
代碼如下：
#include <cstdio>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define maxn 500010
#define ll long long
int n,occ[maxn];
ll val[maxn],ha[maxn],ans=0;
map<ll,int> mp;//存每個哈希值的出現次數
queue<int> q[maxn];
int main()
{
scanf("%d",&n);srand(9904);
for(int i=1;i<=n;i++)val[i]=((ll)rand()<<30)+(rand()<<16)+rand();
int st=0;mp[0ll]++;
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
if(q[x].size()==3){
int to=q[x].front();q[x].pop();
while(st<to)mp[ha[st++]]--;
}
q[x].push(i);
ha[i]=ha[i-1]-occ[x]*val[x];
occ[x]=(occ[x]+1)%3;
ha[i]+=occ[x]*val[x];
ans+=mp[ha[i]];mp[ha[i]]++;
}
printf("%lld",ans);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/58438.html
標籤：其他
上一篇：動態規劃演算法解題思路