北京信息科技大学第十一届程序设计竞赛 部分题解

北京信息科技大学第十一届程序设计竞赛

感觉没有吉首大学那场好玩。
老年选手智商尽失,勉勉强强刷刷水题维持生活。

A kotori和糖果

卡了一天,made竟然是个煞笔题,用map取重剪去搜索节点就可以了,但竟然还会爆INT????
题意:n堆石头,每堆一个,合并的代价是两堆数量差值。求合并成一堆最小代价。
分析:哈夫曼合并树模型,容易推出公式f(n)=f(n/2)+f((n+1)/2)+(n&1),但对于n=1e18运算节点太多重复太多,所以用map处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f;
const int N=1e3+10;
map<long long ,long long >q;
long long fun(long long n)
{
if(n<=2) return q[n]=0;
if(q[n]) return q[n];
return q[n]=fun(n/2)+fun((n+1)/2)+(n&1);
}
int main()
{
int t;
long long n;
scanf("%d",&t);
q.clear();
while(t--)
{
scanf("%lld",&n);
printf("%lld\n",fun(n));
}
return 0;
}

B kotori和气球

题意:n中颜色数量不限的气球,选m个摆成一排,相同颜色不能相邻,方案数对109取余。
分析:ans=n*(n-1)*(n-1)* *** *(n-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int MOD=109;
const int N=1e5+10;
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int ans=n;
for(int i=1;i<m;i++)
ans=ans*(n-1)%MOD;
printf("%d\n",ans);
}
return 0;
}

C kotori和出道

题意:n个人始终成一个环,依次报数,偶数出列,求最后剩下的人是谁。
分析:经典约瑟夫环问题。但这题打个表规律就出来了。

1
2
3
4
5
6
7
8
9
10
import math
while True:
try:
t=int(input())
for i in range(t):
n=int(input())
x=int(math.log2(n))
n=n-2**x
print(2*n+1)
except:break

D kotori和迷宫

题意:意思就是从起点开始搜,到了出口’e’就直接出去,求能到达的出口数量和最近出口的距离。
分析:在广搜的基础上加一句即可,判断当前点是否为出口’e’,是直接continue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
const int MOD=109;
const int N=1e5+10;
int n,m,ans1,ans2,vis[55][55];
char s[55][55];
struct node
{
int x,y,step;
};
queue<node>q;
void bfs(int x,int y,int step)
{
ans1=0,ans2=90;
node tmp;
tmp.x=x,tmp.y=y,tmp.step=0;
memset(vis,0,sizeof(vis));
while(!q.empty()) q.pop();
q.push(tmp);
while(!q.empty())
{
tmp=q.front();
q.pop();
if(vis[tmp.x][tmp.y]) continue;
vis[tmp.x][tmp.y]=1;
if(s[tmp.x][tmp.y]=='e')
{
ans1++;
ans2=min(ans2,tmp.step);
continue;
}
if(tmp.x-1>0&&s[tmp.x-1][tmp.y]!='*'&&!vis[tmp.x-1][tmp.y])
q.push(node{tmp.x-1,tmp.y,tmp.step+1});
if(tmp.x+1<=n&&s[tmp.x+1][tmp.y]!='*'&&!vis[tmp.x+1][tmp.y])
q.push(node{tmp.x+1,tmp.y,tmp.step+1});
if(tmp.y-1>0&&s[tmp.x][tmp.y-1]!='*'&&!vis[tmp.x][tmp.y-1])
q.push(node{tmp.x,tmp.y-1,tmp.step+1});
if(tmp.y+1<=m&&s[tmp.x][tmp.y+1]!='*'&&!vis[tmp.x][tmp.y+1])
q.push(node{tmp.x,tmp.y+1,tmp.step+1});
}
if(ans1==0) puts("-1");
else printf("%d %d\n",ans1,ans2);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
int sx,sy;
for(int i=1; i<=n; i++)
{
scanf("%s",s[i]+1);
for(int j=1; j<=m; j++)
if(s[i][j]=='k')
sx=i,sy=j;
}
bfs(sx,sy,0);
}
return 0;
}

E kotori和素因子

  • 题意:n≤10个数,每个数≤1000。从每个数中选出一个素因子,要求所选出的所有素因子不同。求这些素因子的和的最小值。
  • 分析:正解是暴搜即可。1000以内的数每个数由最多5个素因子之积组成,那么暴力的复杂度是510=9765625。
  • 题解2:费用流模型。源点0到[1-n]这n个数分别建边容量为1,费用为0;n个数每个数分别与它的素因子建边,容量为1,费用为0(或1,这样素因子到汇点的费用为0即可);素因子到汇点T建边,容量为1,费用为素因子大小。
  • 想想看这样为什么费用流模型可以?费用流模型在最大流的基础上求最小费用,流量自然是我们这n个数每个数都要选一个,我们给每个数i都创建流量为1的通路,那么最终最大流量就是n,不到n输出-1;费用是素因子对答案的贡献,当一个数有多个素因子时就有多个选择,那么费用流模型会自动找寻增广轨寻求费用最小的那条通道。费用流模型能解决更大的数据范围,具体没算。被自己的机智折服。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    #include<bits/stdc++.h>
    using namespace std;
    const int INF=0x3f3f3f;
    const int N=1e3+10;
    struct Edge
    {
    int to,next,cap,flow,cost;
    } e[N*10];
    int head[N],tot,tn;
    int pre[N],dis[N];
    int vis[N];
    void init(int num)
    {
    tot=0;//边的数量
    tn=num;
    memset(head,-1,sizeof(head));
    }
    void add(int u,int v,int cap,int cost)
    {
    e[tot].to=v,e[tot].cap=cap,e[tot].cost=cost,e[tot].flow=0;
    e[tot].next=head[u];
    head[u]=tot++;
    e[tot].to=u,e[tot].cap=0,e[tot].cost=-cost,e[tot].flow=0;
    e[tot].next=head[v];
    head[v]=tot++;
    }
    bool spfa(int s,int t)
    {
    queue<int>q;
    for(int i=0; i<=tn; i++)
    {
    dis[i]=INF;
    vis[i]=0;
    pre[i]=-1;
    }
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
    int u=q.front();
    q.pop();
    vis[u]=0;
    for(int i=head[u]; i+1; i=e[i].next)
    {
    int v=e[i].to;
    if(e[i].cap>e[i].flow&&dis[v]>dis[u]+e[i].cost)
    {
    dis[v]=dis[u]+e[i].cost;
    pre[v]=i;
    if(!vis[v])
    {
    vis[v]=1;
    q.push(v);
    }
    }
    }
    }
    if(pre[t]==-1) return false;
    return true;
    }
    void mincost_maxflow(int s,int t,int n)
    {
    int cost=0;
    int flow=0;
    while(spfa(s,t))
    {
    int Min=INF;
    for(int i=pre[t]; i!=-1; i=pre[e[i^1].to])
    if(Min>e[i].cap-e[i].flow)
    Min=e[i].cap-e[i].flow;
    for(int i=pre[t]; i!=-1; i=pre[e[i^1].to])
    {
    e[i].flow+=Min;
    e[i^1].flow-=Min;
    cost+=e[i].cost*Min;
    }
    flow+=Min;
    }
    if(flow<n||flow>=INF) puts("-1");
    else printf("%d\n",cost);
    }
    int prime[1003],Vis[1003];
    int a[50];
    int main()
    {
    int n,cnt=0;
    memset(prime,-1,sizeof(prime));
    prime[0]=prime[1]=0;
    for(int i=2; i<=1000; i++)
    if(prime[i])
    {
    for(int j=i*i; j<=1000; j+=i)
    prime[j]=0;
    prime[cnt++]=i;
    }
    while(~scanf("%d",&n))
    {
    memset(Vis,0,sizeof(Vis));
    int Cnt=0;
    for(int i=1; i<=n; i++)
    {
    scanf("%d",&a[i]);
    for(int j=0; j<cnt; j++)
    if(a[i]%prime[j]==0&&Vis[prime[j]]==0)
    Vis[prime[j]]=++Cnt;
    }
    init(1+n+Cnt+2);
    for(int i=1; i<=n; i++)
    {
    add(0,i,1,0); //源点到i
    for(int j=0; j<cnt; j++)
    if(a[i]%prime[j]==0)
    add(i,n+Vis[prime[j]],1,prime[j]); //i到素因子
    }
    for(int j=0; j<cnt; j++)
    if(Vis[prime[j]])
    add(n+Vis[prime[j]],n+Cnt+2,1,0); //素因子到汇点
    mincost_maxflow(0,n+Cnt+2,n);
    }
    return 0;
    }

H andy和购物

题意:水题,排序计算内积即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while True:
try:
t=int(input())
for i in range(t):
n=int(input())
a=list(map(int,input().split()))
b=list(map(float,input().split()))
a.sort()
b.sort(reverse=True)
ans=0
for j in range(n):
ans=ans+a[j]*b[j]
print('%.3f'%ans)
except:break

I andy种树

题意:每次选一个区间加一,然后最后想知道1-n每个坐标的数是多少。
分析:会线段树用线段树区间更新单点查询裸题。不会线段树用左家右减法即可,区间左端点加1,区间右端点再往右一个的位置减一,最后累加。烂大街的技巧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int N=1e6+10;
int a[N];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(a,0,sizeof(a));
int l,r;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
a[l]++;
a[r+1]--;
}
for(int i=1;i<=n;i++)
{
a[i]+=a[i-1];
printf("%d%c",a[i],i==n?'\n':' ');
}
}
return 0;
}

J andy的树被砍了

题意:煞笔题还想好好伪装。
分析:伤害直接累加,然后求某棵树先加上对应前一个的累加伤害值,再在伤害数组中lower_bound()二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int N=1e6+10;
long long a[N],b[N];
int n;
int main()
{
while(~scanf("%d",&n))
{
a[0]=b[0]=0;
for(int i=1; i<=n; i++)
scanf("%lld",&a[i]);
for(int i=1; i<=n; i++)
{
scanf("%lld",&b[i]);
b[i]+=b[i-1];
}
for(int i=1; i<=n; i++)
{
int pos=lower_bound(b+1,b+n+1,a[i]+b[i-1])-b;
printf("%d%c",pos,i==n?'\n':' ');
}
}
return 0;
}