QBXT金秋試験問題解qwq
5618 ワード
game
期待を押すだけでいい.
2つの特判は保底分用のqwqを残します
#include
#include
using namespace std;
int n;
double p[1001][1001], ans, g[1001][1001];
int main(){
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
scanf("%d", &n);
for(int i=1; i<=n; i++)
for(int j=0; j cake
meet in middle.二つの半分に分けてサブセットの二重ポインタを列挙して判断すればよい.
(阿克王poorpoolのコード!:
#include
#include
#include
using namespace std;
int n, X, a[25], b[25], aa, bb, cnta, cntb, vala[1048595], valb[1048595], tmp;
int main(){
freopen("cake.in", "r", stdin);
freopen("cake.out", "w", stdout);
cin>>n>>X;
aa = n / 2;
bb = n - aa;
for(int i=1; i<=aa; i++)
scanf("%d", &a[i]);
for(int i=1; i<=bb; i++)
scanf("%d", &b[i]);
for(int i=0; iX) break;
}
if(tmp<=X) vala[++cnta] = tmp;
}
for(int i=0; iX) break;
}
if(tmp<=X) valb[++cntb] = tmp;
}
sort(vala+1, vala+1+cnta);
sort(valb+1, valb+1+cntb);
int i=1, j=cntb, ans=X;
for(; i<=cnta; i++){
while(vala[i]+valb[j]>X && j>0) j--;
if(!j) break;
ans = min(ans, X-vala[i]-valb[j]);
}
cout< grid
50点までだませばいい.
road
明らかにsをルートとして木を建てた.xからLCAに変更するかyからLCAに変更するかを考えるだけです.それぞれmaxを求める.
考えが倍増する.接頭辞および(sum(i)(i)(i)で点(i)からルートへの辺権和,(f(i,j)(i)を接頭辞および(sum(i)(i)でジャンプ(2^j)が次に到達した点,(fsum(i,j))は(i)点から(f(i,j))点への辺権和,(road(i,j))は(i)点から(f(i,j))点への経路上で、最良の(c(c)から得られた最も優れた(i)から(i)への経路上に、(i)から(i)から(i)点への経路上から(c)のパス上の重み和.
これらをうまく処理するには、質問するたびに簡単です.
#include
#include
#define maxn 2000001
using namespace std;
inline int qr(){
int x=0, f=1;
char ch=getchar();
for(;!isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
for(; isdigit(ch); ch=getchar()) x=(x<<3)+(x<<1)+ch-48;
return x*f;
}
int n, head[maxn], tot;
int q, s;
struct edge{
int to, nxt, val;
}e[maxn];
int f[maxn][20], dep[maxn];
int sum[maxn];
int road[maxn][20];
int fsum[maxn][20];
void add(int u, int v, int w){
e[++tot].nxt=head[u];
e[tot].to=v;
e[tot].val=w;
head[u]=tot;
}
void LCA_fst(int u, int fa){
dep[u]=dep[fa]+1;
for(int i=0; i<18; i++){
f[u][i+1]=f[f[u][i]][i];
fsum[u][i+1]=fsum[f[u][i]][i]+fsum[u][i];
road[u][i+1]=min(road[u][i], fsum[u][i]+road[f[u][i]][i]);
}
for(int i=head[u]; i; i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
f[v][0]=u;
sum[v]=sum[u]+e[i].val;
fsum[v][0]=e[i].val;
road[v][0]=min(0, e[i].val);
LCA_fst(v, u);
}
}
int LCA(int x, int y){
if(dep[x]=0; i--)
if(f[x][i]!=0&&dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y)return x;
for(int i=18; i>=0; i--)
if(f[x][i]!=0&&f[y][i]!=0&&f[x][i]!=f[y][i])
x=f[x][i], y=f[y][i];
return f[x][0];
}
int solve(int x, int y){
int ans=0, road_sum=0;
for(int i=18; i>=0; i--){
if(f[x][i]!=0&&dep[f[x][i]]>=dep[y]){
ans=min(ans, road_sum+road[x][i]);
road_sum+=fsum[x][i];
x=f[x][i];
}
}
return ans;
}
int main(){
freopen("road.in", "r", stdin);
freopen("road.out", "w", stdout);
n=qr(), q=qr(), s=qr();
int a, b, c;
for(int i=1; i bride
2層列挙.まず賄賂を受け取る可能性がある人を列挙し、一人一人が支持するかどうかを列挙し、確率を求めてminを取ればいい.
なぜか一つ間違えた.90pts:
#include
#include
#include
using namespace std;
inline int qr(){
int x=0, f=1;
char ch=getchar();
for(;!isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
for(; isdigit(ch); ch=getchar()) x=(x<<3)+(x<<1)+ch-48;
return x*f;
}
int n, k, a;
int w[10], h[10];
double ans, P;
void dfs2(double pro, int cur, int sum, int support){
if(cur==n+1){
if(support>0) P+=pro*a/(a+sum);
else P+=pro;
}else{
dfs2(pro*h[cur]/100, cur+1, sum+w[cur], support+1);
dfs2(pro*(100-h[cur])/100, cur+1, sum, support-1);
}
}
void dfs(int cur, int used){
if(used==k){
P=0.0;
dfs2(1.0, 1, 0, 0);
ans=max(ans, P);
return;
}
for(int i=cur; i<=n; i++){
if(h[i]>=10){
h[i]-=10;
dfs(i, used+1);
h[i]+=10;
}
}
}
int main(){
freopen("bride.in", "r", stdin);
freopen("bride.out", "w", stdout);
n=qr(), k=qr(), a=qr();
for(int i=1; i<=n; i++)
w[i]=qr(), h[i]=qr();
dfs(1, 0);
printf("%.6f", 1.0-ans);
return 0;
} climb
いろいろな奇妙な暴力の艹は点数を騙すことができる.(実はこの問題はD 2で一番できる問題qwqです
転載先:https://www.cnblogs.com/pushinl/p/9929417.html