The Preliminary Contest for ICPC Asia Shenyang 2019
B Dudu's maze
题目链接
题意：n个点,m条边构成一张图，每个点都是一个房间，房间里可能有糖果和怪兽，再给出人的初始位置（保证初始位置为糖果屋）。人具有一点魔法值，当其走到糖果屋时，可以拿走糖果，当其走到怪兽屋，可以用魔法值转移到相邻房间，或者退出迷宫，求退出迷宫时，拿到糖果的期望。
思路：并查集所有联通糖果屋，搜索联通块再计算期望。
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,k;
int fa[maxn];
int sz[maxn];
int u[maxn<<1],v[maxn<<1];
int vis[maxn];;
int book[maxn];
vector <int>G[maxn];
vector <int>vt;
void init(int n){
for(int i=1;i<=n;i++){
fa[i]=i;
vis[i]=0;
sz[i]=1;
G[i].clear();
book[i]=0;
}
vt.clear();
}
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void mix(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
fa[fx]=fy;
sz[fy]+=sz[fx];
sz[fx]=0;
}
}
void bfs(int x){
queue <int>q;
book[x]=1;
q.push(x);
while(!q.empty()){
int f=q.front();
q.pop();
for(int i=0;i<G[f].size();i++){
if(book[G[f][i]]){
continue;
}
if(!vis[G[f][i]]){
q.push(G[f][i]);
book[G[f][i]] = 1;
}else
vt.push_back(G[f][i]);
}
}
}
void input(){
scanf("%d%d%d",&n,&m,&k);
int i,x;
init(n);
for(i=0;i<m;i++){
scanf("%d%d",&u[i],&v[i]);
G[u[i]].push_back(v[i]);
G[v[i]].push_back(u[i]);
}
for(i=1;i<=k;i++)
{
scanf("%d",&x);
vis[x]=1;
sz[x] = 0;
}
for(i=0;i<m;i++){
if(!vis[find(u[i])]&&!vis[find(v[i])]){
mix(u[i],v[i]);
}
}
}
void solve(){
double store = sz[find(1)];
sz[find(1)] = 0;
bfs(1);
int siz = vt.size();
long long temp;
double ans = 0, esum;
for(int i = 0;i < siz;i++){
esum = G[vt[i]].size();
temp = 0;
for(int j = 0;j < esum;j++){
temp += sz[find(G[vt[i]][j])];
//cout << find(G[vt[i]][j]) << " " << sz[find(G[vt[i]][j])] << endl;
}
//cout << temp << " " << esum << endl;
if(temp * 1.0 / esum> ans){
ans = temp * 1.0 / esum;
}
}
printf("%.8lf\n",ans + store);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
input();
solve();
}
}
/*4 4 2
1 2
2 3
3 4
4 1
2 3*/ C Dawn-K's water
题目链接
完全背包+枚举
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll p[1003], c[1004];
ll dp[20004];
int main() {
ll n, m;
while (~scanf("%lld%lld", &n, &m)) {
//n = 1000; m = 1e4;
ll ma = 0;
for (ll i = 1; i <= n; i++) {
scanf("%lld%lld", &p[i], &c[i]);
ma = max(c[i], ma);
// p[i] = 1e9;c[i] = 1;
}
memset(dp, inf, sizeof dp);
ll M = max(ma * 2, m * 2);
dp[0] = 0;
for (ll i = 1; i <= n; i++) {
for (ll j = c[i]; j <= M; j++) {
if (dp[j] > dp[j - c[i]] + p[i]) {
dp[j] = dp[j - c[i]] + p[i];
}
}
}
ll ans1 = inf, ans2 = -1;
for (ll i = m; i <= M; i++) {
if (ans1 > dp[i]) {
ans1 = dp[i];
ans2 = i;
}
else if (ans1 == dp[i]) {
ans2 = i;
}
}
printf("%lld %lld\n", ans1, ans2);
}
}
/*
3 3
2 1
3 1
1 1
3 5
1 2
2 3
3 3
*/ D Fish eating fruit
题目链接
题意：n个点构成一颗树，求两点之间边权%3余0、余1、余2的边权值总和
思路：正解，树形dp。也可用点分治做。对于分治得到每个树，记录当前的余0、余1、余2的边权个数，通过个数可以得到组合后的各个权值总和。点分治、容斥子树得到最后答案。
#include <bits/stdc++.h>
#define maxn 100005
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int mod=1000000007;
struct edge{
int to;ll cost;int next;
};
edge G[maxn<<1];
int head[maxn];
int edgeNum;
int mx,rt;
int Size;
int sz[maxn];
int book[maxn];
ll sum[3];
ll ans[3];
ll fin[3];
int n,u,v,w;
void add_edge(int a,int b,int c){
G[edgeNum].to=b;
G[edgeNum].cost=c;
G[edgeNum].next=head[a];
head[a]=edgeNum++;
}
void dfsroot(int u,int fa){
sz[u]=1;
int num=0;
for(int i=head[u];i!=-1;i=G[i].next){
int v=G[i].to;
if(book[v]||v==fa)
continue;
dfsroot(v,u);
sz[u]+=sz[v];
num=max(num,sz[v]);
}
num=max(num,Size-sz[u]);
if(num<mx){
mx=num;
rt=u;
}
}
void query(int u,int fa,ll val){
sum[val%3]++;
ans[val%3]+=val;
for(int i=head[u];i!=-1;i=G[i].next){
int v=G[i].to;
if(v==fa||book[v])
continue;
query(v,u,(val+G[i].cost));
}
}
void solve(int u,ll val,int flag){
// cout<<"U"<<u<<' '<<flag<<endl;
sum[0]=sum[1]=sum[2]=0;
ans[0]=ans[1]=ans[2]=0;
query(u,-1,val);
// cout<<"!!!"<<sum[0]<<' '<<sum[1]<<' '<<sum[2]<<endl;
// cout<<"???"<<ans[0]<<' '<<ans[1]<<' '<<ans[2]<<endl;
ll temp1,temp2,temp3;
temp1=temp2=temp3=0;
temp1+=ans[0]*(sum[0]-1)+sum[2]*ans[1]+sum[1]*ans[2];
temp2+=ans[2]*(sum[2]-1)+sum[1]*ans[0]+sum[0]*ans[1];
temp3+=ans[1]*(sum[1]-1)+sum[2]*ans[0]+sum[0]*ans[2];
// cout<<temp1<<' '<<temp2<<' '<<temp3<<endl;
if(flag){
fin[0]+=ans[0]+temp1;
fin[1]+=ans[1]+temp2;
fin[2]+=ans[2]+temp3;
fin[0]=fin[0]%mod;
fin[1]=fin[1]%mod;
fin[2]=fin[2]%mod;
}else
{
fin[0]-=ans[0]+temp1;
fin[1]-=ans[1]+temp2;
fin[2]-=ans[2]+temp3;
fin[0]=(fin[0]+mod)%mod;
fin[1]=(fin[1]+mod)%mod;
fin[2]=(fin[2]+mod)%mod;
}
// cout<<fin[0]<<' '<<fin[1]<<' '<<fin[2]<<endl;
}
void devide(int u){
solve(u,0,1);
book[u]=1;
int tot=Size;
for(int i=head[u];i!=-1;i=G[i].next)
{
int v=G[i].to;
if(book[v])
continue;
solve(v,G[i].cost,0);
rt=0;
Size=sz[v]>sz[u]?tot-sz[u]:sz[v];
mx=inf;
dfsroot(v,-1);
devide(rt);
}
}
void input(){
for(int i=1;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
u++;v++;
add_edge(u,v,w);
add_edge(v,u,w);
}
}
void solve(){
Size=n;
mx=inf;
dfsroot(1,0);
devide(rt);
}
int main(){
while(scanf("%d",&n)!=EOF){
memset(head,-1,sizeof head);
memset(fin,0,sizeof fin);
memset(book,0,sizeof book);
memset(sz,0,sizeof sz);
edgeNum=0;
input();
solve();
printf("%lld %lld %lld\n",fin[0]*2%mod,fin[1]*2%mod,fin[2]*2%mod);
}
} F Honk's pool
题目链接
题意：每次挑出最大的，令其减一，然后挑出最小的，令其加一。共操作 K 次，求最大值和最小值的差。
思路：二分
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 1000002
const int INF = 0x3f3f3f3f;
using namespace std;
int num[maxn * 5];
ll pre[maxn * 5];
int main(void){
ll n, k, i, add, sub, l, r, m, pos;
ll sum;
num[0] = -1;
pre[0] = 0;
while(scanf("%lld %lld",&n,&k)!=EOF){
for(i = 1;i <= n;i++){
scanf("%lld",&num[i]);
}
num[n + 1] = 1e9 + 7;
sort(num + 1,num + n + 1);
for(i = 1;i <= n;i++){
pre[i] = pre[i - 1] + num[i];
}
sum = pre[n];
l = 0;
r = 1e9 + 1;
while(l <= r){
m = (l + r) >> 1;
pos = lower_bound(num,num + n + 1,m) - num - 1;
if(sum - pre[pos] - (n - pos) * m > k){
l = m + 1;
}
else{
r = m - 1;
}
}
sub = l;
l = 0;
r = 1e9 + 1;
while(l <= r){
m = (l + r) >> 1;
pos = upper_bound(num,num + n + 1,m) - num - 1;
if(m * pos - pre[pos] > k){
r = m - 1;
}
else{
l = m + 1;
}
}
add = r;
if(add >= sub){
if(pre[n] % n == 0){
puts("0");
}
else{
puts("1");
}
}
else{
printf("%d\n",sub - add);
}
}
return 0;
} H Texas hold'em Poker
题目链接
题意：打牌顺子、对子。。等若干规则，给出规则排序。
思路：模拟
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n;
struct node{
char name[10];
int p[5];
int level;
int sum1=0;
int level2=0,sum2=0;
int level31=0,level32=0,sum3=0;
int level4=0,sum4=0;
int level5=0,sum5=0;
int level6=0,sum6=0;
}nod[maxn];
void calc(char s[],int index,int len){
int cnt=0;
for(int i=0;i<len;i++){
if(s[i]>='2'&&s[i]<='9'){
nod[index].p[cnt]=s[i]-'0';
}
if(s[i]=='A')
nod[index].p[cnt]=1;
if(s[i]=='J')
nod[index].p[cnt]=11;
if(s[i]=='Q')
nod[index].p[cnt]=12;
if(s[i]=='K')
nod[index].p[cnt]=13;
if(s[i]=='1')
{
nod[index].p[cnt]=10;
i++;
}
cnt++;
}
sort(nod[index].p,nod[index].p+5);
}
void calclevel(int index){
if(nod[index].p[0]==1&&nod[index].p[1]==10&&nod[index].p[2]==11&&nod[index].p[3]==12&&nod[index].p[4]==13){
nod[index].level=8;
return ;
}
if(nod[index].p[0]==nod[index].p[1]-1&&nod[index].p[1]==nod[index].p[2]-1&&nod[index].p[2]==nod[index].p[3]-1&&nod[index].p[3]==nod[index].p[4]-1)
{
nod[index].level=7;
return;
}
if((nod[index].p[0]==nod[index].p[1]&&nod[index].p[0]==nod[index].p[2]&&nod[index].p[0]==nod[index].p[3])||(nod[index].p[4]==nod[index].p[1]&&nod[index].p[4]==nod[index].p[2]&&nod[index].p[4]==nod[index].p[3])){
nod[index].level=6;
if(nod[index].p[0]==nod[index].p[1]&&nod[index].p[0]==nod[index].p[2]&&nod[index].p[0]==nod[index].p[3]){
nod[index].level6=nod[index].p[0];
nod[index].sum6=nod[index].p[4];
}
if(nod[index].p[4]==nod[index].p[1]&&nod[index].p[4]==nod[index].p[2]&&nod[index].p[4]==nod[index].p[3]){
nod[index].level6=nod[index].p[4];
nod[index].sum6=nod[index].p[0];
}
return;
}
if((nod[index].p[0]==nod[index].p[1]&&nod[index].p[0]==nod[index].p[2]&&nod[index].p[3]==nod[index].p[4])||(nod[index].p[2]==nod[index].p[3]&&nod[index].p[2]==nod[index].p[4]&&nod[index].p[0]==nod[index].p[1])){
nod[index].level=5;
if(nod[index].p[0]==nod[index].p[1]&&nod[index].p[0]==nod[index].p[2]&&nod[index].p[3]==nod[index].p[4]){
nod[index].level5=nod[index].p[0];
nod[index].sum5=nod[index].p[3];
}
if(nod[index].p[2]==nod[index].p[3]&&nod[index].p[2]==nod[index].p[4]&&nod[index].p[0]==nod[index].p[1]){
nod[index].level5=nod[index].p[2];
nod[index].sum5=nod[index].p[0];
}
return;
}
if((nod[index].p[0]==nod[index].p[1]&&nod[index].p[0]==nod[index].p[2])||(nod[index].p[1]==nod[index].p[2]&&nod[index].p[1]==nod[index].p[3])||(nod[index].p[2]==nod[index].p[3]&&nod[index].p[2]==nod[index].p[4])){
nod[index].level=4;
if(nod[index].p[0]==nod[index].p[1]&&nod[index].p[0]==nod[index].p[2]){
nod[index].level4=nod[index].p[0];
nod[index].sum4=nod[index].p[3]+nod[index].p[4];
}
if(nod[index].p[1]==nod[index].p[2]&&nod[index].p[1]==nod[index].p[3]){
nod[index].level4=nod[index].p[1];
nod[index].sum4=nod[index].p[0]+nod[index].p[4];
}
if(nod[index].p[2]==nod[index].p[3]&&nod[index].p[2]==nod[index].p[4]){
nod[index].level4=nod[index].p[2];
nod[index].sum4=nod[index].p[0]+nod[index].p[1];
}
return;
}
if((nod[index].p[0]==nod[index].p[1]&&nod[index].p[2]==nod[index].p[3])||(nod[index].p[0]==nod[index].p[1]&&nod[index].p[3]==nod[index].p[4])||(nod[index].p[1]==nod[index].p[2]&&nod[index].p[3]==nod[index].p[4])){
nod[index].level=3;
if(nod[index].p[0]==nod[index].p[1]&&nod[index].p[2]==nod[index].p[3]){
nod[index].level31=nod[index].p[0];
nod[index].level32=nod[index].p[2];
if(nod[index].level31<nod[index].level32)
swap(nod[index].level31,nod[index].level32);
nod[index].sum3=nod[index].p[4];
}
if(nod[index].p[0]==nod[index].p[1]&&nod[index].p[3]==nod[index].p[4]){
nod[index].level31=nod[index].p[0];
nod[index].level32=nod[index].p[3];
if(nod[index].level31<nod[index].level32)
swap(nod[index].level31,nod[index].level32);
nod[index].sum3=nod[index].p[2];
}
if(nod[index].p[1]==nod[index].p[2]&&nod[index].p[3]==nod[index].p[4]){
nod[index].level31=nod[index].p[1];
nod[index].level32=nod[index].p[3];
if(nod[index].level31<nod[index].level32)
swap(nod[index].level31,nod[index].level32);
nod[index].sum3=nod[index].p[0];
}
return;
}
if((nod[index].p[0]==nod[index].p[1])||(nod[index].p[1]==nod[index].p[2])||(nod[index].p[2]==nod[index].p[3])||(nod[index].p[3]==nod[index].p[4])){
nod[index].level=2;
if(nod[index].p[0]==nod[index].p[1]){
nod[index].level2=nod[index].p[0];
nod[index].sum2=nod[index].p[2]+nod[index].p[3]+nod[index].p[4];
}
if(nod[index].p[1]==nod[index].p[2]){
nod[index].level2=nod[index].p[1];
nod[index].sum2=nod[index].p[0]+nod[index].p[3]+nod[index].p[4];
}
if(nod[index].p[2]==nod[index].p[3]){
nod[index].level2=nod[index].p[2];
nod[index].sum2=nod[index].p[1]+nod[index].p[0]+nod[index].p[4];
}
if(nod[index].p[3]==nod[index].p[4]){
nod[index].level2=nod[index].p[3];
nod[index].sum2=nod[index].p[1]+nod[index].p[2]+nod[index].p[0];
}
return;
}
nod[index].level=1;
nod[index].sum1=nod[index].p[0]+nod[index].p[1]+nod[index].p[2]+nod[index].p[3]+nod[index].p[4];
return;
}
bool cmp(node a,node b){
if(a.level==b.level){
if(a.level==1){
if(a.sum1==b.sum1)
return strcmp(a.name,b.name)<0;
return a.sum1>b.sum1;
}else if(a.level==2){
if(a.level2==b.level2){
if(a.sum2==b.sum2)
return strcmp(a.name,b.name)<0;
return a.sum2>b.sum2;
}
return a.level2>b.level2;
}else if(a.level==3){
if(a.level31==b.level31){
if(a.level32==b.level32){
if(a.sum3==b.sum3)
return strcmp(a.name,b.name)<0;
return a.sum3>b.sum3;
}
return a.level32>b.level32;
}
return a.level31>b.level31;
}else if(a.level==4){
if(a.level4==b.level4){
if(a.sum4==b.sum4)
return strcmp(a.name,b.name)<0;
return a.sum4>b.sum4;
}
return a.level4>b.level4;
}else if(a.level==5){
if(a.level5==b.level5){
if(a.sum5==b.sum5)
return strcmp(a.name,b.name)<0;
return a.sum5>b.sum5;
}
return a.level5>b.level5;
}else if(a.level==6){
if(a.level6==b.level6){
if(a.sum6==b.sum6)
return strcmp(a.name,b.name)<0;
return a.sum6>b.sum6;
}
return a.level6>b.level6;
}else if(a.level==7){
if(a.p[4]==b.p[4])
return strcmp(a.name,b.name)<0;
return a.p[4]>b.p[4];
}else{
return strcmp(a.name,b.name)<0;
}
}
return a.level>b.level;
}
void input(){
int i;
char s[10];
for(i=1;i<=n;i++){
scanf("%s%s",nod[i].name,s);
int len=strlen(s);
calc(s,i,len);
calclevel(i);
// for(int j=0;j<5;j++)
// cout<<nod[i].p[j]<<endl;
}
}
void solve(){
sort(nod+1,nod+n+1,cmp);
for(int i=1;i<=n;i++){
printf("%s\n",nod[i].name);
// cout<<nod[i].level<<endl;
}
}
int main(){
while(scanf("%d",&n)!=EOF){
input();
solve();
}
} K Guanguan's Happy water
题目链接
题意：水过
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
ll a[maxn];
ll qpow(ll A, ll B) {
ll t = 1;
while (B) {
if ((B & 1)) {
t = t * A%mod;
}
A = A * A%mod;
B = B >> 1;
}
return t;
}
int main() {
//prllf("%lld\n",5LL*qpow())
ll t;
scanf("%lld", &t);
while (t--) {
ll k, n;
scanf("%lld%lld", &k, &n);
ll K = k * 2;
ll sum = 0;
ll sm = 0;
ll sum2 = 0;
for (ll i = 1; i <= K; i++) {
scanf("%lld", &a[i]);
if (i <= n)sm += a[i];
if (i > k)sum2 += a[i];
sum += a[i];
sum %= mod;
sum2 %= mod;
sm %= mod;
}
ll ans = sm % mod;
if (n >= K) {
ans = (sum2%mod * qpow(k, mod - 2) % mod*((n - K) % mod) % mod + sum % mod) % mod;
}
printf("%lld\n", ans);
}
}
京公网安备 11010502036488号