当前位置：网站首页>2022/7/28
2022/7/28
2022-07-31 10:36:00 【killer_queen4804】
E-Music Game_dp
dp[i]表示前i个的期望是多少，第i个失败的话就是dp[i]=dp(i-1)*(100-p[i]),成功的话就要去枚举起点，所以方程就是![dp[i]=dp[i-1]*(1-p_{i})+\sum_{j=1}^{i}[((i-j+1)^{m}+dp[j-2])*(1-p_{j-1})*\prod_{k=j}^{i}p_{k}]](http://img.inotgo.com/imagesLocal/202207/31/202207311036319048_0.gif)
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll n,m,p[1005],dp[1005],mul[1005][1005];
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main(){
ll inv=qpow(100,mod-2);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>p[i],mul[i][i]=p[i]*inv%mod;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
mul[i][j]=(mul[i][j-1]*p[j]%mod)*inv%mod;
for(int i=1;i<=n;i++){
dp[i]=(dp[i-1]*(100-p[i])%mod)*inv%mod;
for(int j=1;j<=i;j++){
dp[i]=(dp[i]+(((qpow(i-j+1,m)+dp[j-2])%mod)*((100-p[j-1])*inv%mod)%mod)*mul[j][i]%mod)%mod;
}
}
printf("%lld\n",dp[n]);
system("pause");
return 0;
}
1249C2 - Good Numbers (hard version)
其实是和二进制差不多的，但是3进制会有2这个余数，而题目中又说不能有重复的，所以碰到2的话比该位高的最近的0改为1，其后全改为0就可以啦
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll q,n,fac[66],vis[66];
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main(){
fac[0]=1;
for(int i=1;i<=39;i++) fac[i]=fac[i-1]*3LL;
cin>>q;
while(q--){
cin>>n;
for(int i=0;i<=40;i++) vis[i]=0;
ll sup=upper_bound(fac,fac+39,n)-fac;
ll x=sup-1,y=n;
while(y){
while(x>=0&&y<fac[x]) x--;
if(x<0) break;
vis[x]=y/fac[x];
y%=fac[x];
}
ll zero;
for(int i=sup;i>=0;i--){
//cout<<vis[i]<<" "<<i<<endl;
if(vis[i]==0) zero=i;
if(vis[i]>1){
vis[zero]=1;
for(int j=zero-1;j>=0;j--) vis[j]=0;
break;
}
}
ll ans=0;
for(int i=0;i<=sup;i++)
if(vis[i]) ans+=fac[i];
printf("%lld\n",ans);
}
system("pause");
return 0;
}
1458A - Row GCD gcd的性质
gcd的一条性质关于辗转相除法的：gcd(a,b)=gcd(a,b-a),gcd(a,b,c)=gcd(a,b-a,c-b);
所以该题gcd(a[1]+b[j],a[2]+b[j],a[3]+b[j])=gcd(a[1]+b[j],a[2]-a[1],a[3]-a[2]);
1459C. Row GCD（经典数论）_a碟的博客-CSDN博客
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll n,m,a[200005],b[200005];
int main(){
cin>>n>>m;
ll q=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
q=a[2]-a[1];
for(int i=3;i<=n;i++) q=__gcd(q,abs(a[i]-a[i-1]));
for(int i=1;i<=m;i++){
cin>>b[i];
if(n==1){
printf("%lld\n",a[1]+b[i]);continue;
}
printf("%lld ",__gcd(a[1]+b[i],q));
}
system("pause");
return 0;
}
C-公因子_牛客练习赛66 (nowcoder.com)gcd的性质
也上一题类似，用的是一个性质，这次只要关注a[1]的取值就行了，但貌似只有排完序求得x的最小值是正确的
Row GCD(差分+辗转相减法)_一个石马农的博客-CSDN博客
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll n,a[1000006];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
ll g=abs(a[2]-a[1]);
for(int i=3;i<=n;i++) g=__gcd(g,abs(a[i]-a[i-1]));
if(a[1]>=0) printf("%lld %lld\n",g,g-a[1]%g);
else printf("%lld %lld\n",g,abs(a[1])%g);
system("pause");
return 0;
}
4302 Interval GCD (zzstep.com)线段树，树状数组，gcd的性质
也是用到了上面的那条性质，线段树维护a数组的差分数组的gcd，这样每次修改一个区间[x,y]只需要修改x,和y+1就行，树状数组维护差分数组的前缀和方便求答案
Interval GCD（线段树区间增加、区间查询）_sunday_soft的博客-CSDN博客
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll n,m,a[500005],b[500005],t[500005<<2],ta[5000005];
void pushup(ll p){t[p]=__gcd(t[p<<1],t[p<<1|1]);}
void build(ll l,ll r,ll p){
if(l==r){t[p]=b[l];return;}
ll mid=l+r>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
pushup(p);
}
void update(ll l,ll r,ll x,ll y,ll p){
if(l==r){t[p]+=y;return;}
ll mid=l+r>>1;
if(x<=mid) update(l,mid,x,y,p<<1);
else update(mid+1,r,x,y,p<<1|1);
pushup(p);
}
ll query(ll l,ll r,ll L,ll R,ll p){
if(L<=l&&r<=R) return abs(t[p]);
ll mid=l+r>>1;
ll val=0;
if(L<=mid) val=__gcd(val,query(l,mid,L,R,p<<1));
if(R>mid) val=__gcd(val,query(mid+1,r,L,R,p<<1|1));
return abs(val);
}
void add(ll x,ll y){
for(int i=x;i<=n;i+=lowbit(i))
ta[i]+=y;
}
ll ask(ll x){
ll res=0;
for(int i=x;i;i-=lowbit(i))
res+=ta[i];
return res;
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i]-a[i-1];
build(1,n,1);
while(m--){
char op;
ll x,y,z;;
cin>>op;
if(op=='Q'){
scanf("%lld%lld",&x,&y);
ll val=a[x]+ask(x);
printf("%lld\n",__gcd(val,query(1,n,x+1,y,1)));
}
else{
scanf("%lld%lld%lld",&x,&y,&z);
update(1,n,x,z,1),add(x,z);
if(y<n) update(1,n,y+1,-z,1),add(y+1,-z);
}
}
system("pause");
return 0;
}
1444A - Division
p不整除q直接输出p，否则枚举q的质因子，p一直除这个质因子知道p不能整除q，更新最大值
Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad)——C. Division_cll7777777的博客-CSDN博客
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll q,p,t,cnt;
ll pri[1000006],a[1000006],vis[1000006];
bool ispri[1000006];
void prime(ll n){
memset(ispri,1,sizeof(ispri));
ispri[0]=ispri[1]=0;
for(ll i=2;i<=n;i++){
if(ispri[i]) pri[++cnt]=i;
for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
ispri[i*pri[j]]=0;
if(i%pri[j]==0) break;
}
}
}
int main(){
prime(1000000);
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&p,&q);
ll y=q,ct=0;
if(p%q){printf("%lld\n",p);continue;}
for(int i=1;i<=cnt;i++){
if(q%pri[i]==0){
a[++ct]=pri[i];
while(q%pri[i]==0) q/=pri[i];
}
}
if(q>1) a[++ct]=q;
ll x=p,ans=0;
for(int i=1;i<=ct;i++){
x=p;
while(x%y==0&&x%a[i]==0) x/=a[i];
ans=max(x,ans);
}
printf("%lld\n",ans);
}
system("pause");
return 0;
}
1551C - Interesting Story
一共就5个字母，枚举一下如果当前字母的个数大于其他所有个数最多可以用几个单词，枚举的时候如果是当前字母就加1，不是就减1，最后看看能加几个单词
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll t,n,a[200005];
string s[200005];
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
ll ans=0;
for(int i=1;i<=n;i++) cin>>s[i];
for(char c='a';c<='e';c++){
for(int i=1;i<=n;i++) a[i]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<s[i].size();j++)
if(s[i][j]==c) a[i]++;
else a[i]--;
sort(a+1,a+n+1);
ll res=0,sum=0;
for(int i=n;i>=1;i--){
sum+=a[i];
if(sum<=0) break;
res++;
}
ans=max(ans,res);
}
printf("%lld\n",ans);
}
system("pause");
return 0;
}
A-Game_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）（热身赛） 期望
期望的线性性，E(x+y)=E(x)+E(y), 如果每次都是互质的话只需要抽n/2次就够了，只抽一次的话是1/C(n,2),预处理出符合条件的对数cnt，答案就是cnt/C(n,2)*n/2,注意n的奇偶需要判断一下，奇数的话是（n-1)/2次，虽然说计算机的出发两者其实是一样的，但是放到期望里面好像就不一样了
北化ACM集训队-浅谈期望题的做法_哔哩哔哩_bilibili
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll n;
int main(){
ll cnt=0;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(__gcd(i,j)==1) cnt++;
ll p=cnt,q=n-1;
if(n&1) q=n;
printf("%lld/%lld\n",p/__gcd(p,q),q/__gcd(p,q));
system("pause");
return 0;
}
570D - Tree Requests树上启发式合并
和板子是一样的套路，看来启发式合并或许难的不是合并的过程，而是先要想出一个可以适合启发式合并的暴力思路，这个题就是没有想到暴力的思路，其实也就是统计每个深度的各个颜色的个数，然后离线判断每个询问，板子大致一样，也就是统计函数要根据题目来写
题解 CF570D 【Tree Requests】 - 牛蛙丶丶 的幼儿园 - 洛谷博客
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll n,m,tot[500005][27];
ll son[500005],siz[500005],dep[500005],fson,vis[500005];
bool ans[500005];
char s[500005];
struct qq{
ll su,id;
};
vector<qq>q[500005];
ll head[1000006],cnt;
struct Edge{
ll from,to,next;
}edge[1000006];
void addedge(ll from, ll to){
edge[++cnt].from=from;
edge[cnt].to=to;
edge[cnt].next=head[from];
head[from]=cnt;
}
void dfs1(ll u,ll fa){
dep[u]=dep[fa]+1;siz[u]=1;
for(int i=head[u];i;i=edge[i].next){
ll j=edge[i].to;
if(j==fa) continue;
dfs1(j,u);
siz[u]+=siz[j];
if(siz[j]>siz[son[u]]) son[u]=j;
}
}
void cal(ll u,ll fa,ll val){
tot[dep[u]][s[u]-'a']+=val;
for(int i=head[u];i;i=edge[i].next){
ll j=edge[i].to;
//if(j!=fa&&j!=fson) cal(j,u,val);
if(j!=fa&&!vis[j]) cal(j,u,val);
}
}
bool check(ll u){
ll res=0;
for(int i=0;i<26;i++){
if(tot[u][i]&1) res++;
if(res>1) return 0;
}
return 1;
}
void dfs2(ll u,ll fa,ll keep){
for(int i=head[u];i;i=edge[i].next){
ll j=edge[i].to;
if(j!=fa&&j!=son[u]) dfs2(j,u,0);
}
if(son[u]) dfs2(son[u],u,1),vis[son[u]]=1;
cal(u,fa,1);vis[son[u]]=0;
for(int i=0;i<q[u].size();i++) ans[q[u][i].id]=check(q[u][i].su);
if(!keep) cal(u,fa,-1);
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=2;i<=n;i++){
ll u;scanf("%lld",&u);
addedge(u,i);addedge(i,u);
}
scanf("%s",s+1);
dfs1(1,0);
for(int i=1;i<=m;i++){
ll a,b;
scanf("%lld%lld",&a,&b);
q[a].push_back({b,i});
}
dfs2(1,0,1);
for(int i=1;i<=m;i++)
if(ans[i]) printf("Yes\n");
else printf("No\n");
system("pause");
return 0;
} CF208E Blood Cousins -树上启发式合并
新学了个倍增求k级祖先，下面的人讲的还可以，lg[i]就是log2(i)+1,应该就是表示i可以向上跳几次
题解 P3379 【【模板】最近公共祖先（LCA）】 - MorsLin 的博客 - 洛谷博客
找出k级祖先来然后去遍历这个祖先的子树，相同深度的个数减1就是答案，注意这是个森林，所以每个根就要进行dfs
题解 CF208E 【Blood Cousins】 - 坡道旁的向日葵 - 洛谷博客
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll n,m,tot[500005];
ll son[500005],siz[500005],dep[500005],fson;
ll f[100005][30],lg[100005],ans[100005];
struct qq{
ll su,id;
};
vector<qq>q[500005];
ll head[1000006],cnt;
struct Edge{
ll from,to,next;
}edge[1000006];
void addedge(ll from, ll to){
edge[++cnt].from=from;
edge[cnt].to=to;
edge[cnt].next=head[from];
head[from]=cnt;
}
ll kthparent(ll u,ll k){
for(int i=lg[dep[u]];i>=0;i--)
if(dep[u]-dep[f[u][i]]<=k) k-=dep[u]-dep[f[u][i]],u=f[u][i];
return u;
}
void dfs1(ll u,ll fa){
dep[u]=dep[fa]+1;siz[u]=1;
for(int i=1;i<=lg[dep[u]];i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u];i;i=edge[i].next){
ll j=edge[i].to;
if(j==fa) continue;
dfs1(j,u);
siz[u]+=siz[j];
if(siz[j]>siz[son[u]]) son[u]=j;
}
}
void cal(ll u,ll fa,ll val){
tot[dep[u]]+=val;
for(int i=head[u];i;i=edge[i].next){
ll j=edge[i].to;
//if(j!=fa&&j!=fson) cal(j,u,val);
if(j!=fa&&j!=fson) cal(j,u,val);
}
}
void dfs2(ll u,ll fa,ll keep){
for(int i=head[u];i;i=edge[i].next){
ll j=edge[i].to;
if(j!=fa&&j!=son[u]) dfs2(j,u,0);
}
if(son[u]) dfs2(son[u],u,1),fson=son[u];
cal(u,fa,1);fson=0;
for(int i=0;i<q[u].size();i++) ans[q[u][i].id]=tot[dep[q[u][i].su]]-1;
if(!keep) cal(u,fa,-1);
}
int main(){
lg[0]=-1;
for(int i=1;i<=100000;i++) lg[i]=lg[i>>1]+1;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&f[i][0]);
if(f[i][0]) addedge(f[i][0],i),addedge(i,f[i][0]);
}
for(int i=1;i<=n;i++){
if(!f[i][0]) dfs1(i,0);
}
scanf("%lld",&m);
for(int i=1;i<=m;i++){
ll x,p;
scanf("%lld%lld",&x,&p);
q[kthparent(x,p)].push_back(qq{x,i});
}
for(int i=1;i<=n;i++){
if(!f[i][0]) dfs2(i,0,0);
}
for(int i=1;i<=m;i++) printf("%lld ",ans[i]);
system("pause");
return 0;
} 边栏推荐
- 单点登录的三种方式
- Find a Go job in 7 days, Conditional statements to learn in Gopher, loop statements, Part 3
- SQL——左连接（Left join）、右连接（Right join）、内连接（Inner join）
- 【LeetCode】1161.最大层内元素和
- GZIPInputStream 类源码分析
- 「MySQL」- 基础增删改查
- KVM virtualization job
- Meikle Studio--Hongmeng 14-day development training notes (8)
- Three ways of single sign-on
- 【Go事】一眼看穿 Go 的集合和切片
猜你喜欢
![AtCoder—E - Σ[k=0..10^100]floor(X／10^k](/img/be/82cfab00950c1f28d426e76a792906.png)
随机推荐
(C language) program environment and preprocessing
《MySQL高级篇》四、索引的存储结构
实现弹框组件
Emotional crisis, my friend's online dating girlfriend wants to break up with him, ask me what to do
《JUC并发编程 - 高级篇》06 - 共享模型之不可变（不可变类的设计 | 不可变类的使用 | 享元模式）
Web系统常见安全漏洞介绍及解决方案-CSRF攻击
Web系统常见安全漏洞介绍及解决方案-sql注入
Implement a thread pool
Usage of JOIN in MySQL
WEB核心【记录网站登录人数，记录用户名案例】Cookie技术实现
众多mock工具，这一次我选对了
MySQL中JOIN的用法
SQLSERVER merges subquery data into one field
Source code analysis of GZIPInputStream class
Use turtle to draw buttons
SQL——左连接（Left join）、右连接（Right join）、内连接（Inner join）
Module eight
【Go事】一眼看穿 Go 的集合和切片
SQL学习笔记——REGEXP运算符
SQL力扣刷题七