2019 BUAA Summer Training 10 题解

Solved	A	B	C	D	E	F	G	H	I	J	K	L	M
9/13	O	O	Ø	.	O	O	O	O	.	O	.	O	.

• O for passing during the contest
• Ø for passing after the contest
• ! for attempted but failed
• · for having not attempted yet

题目来源：2015 ACM-ICPC Asia Changchun Regional Contest

比赛链接

A Too Rich

题目描述

给定一些价值为$1,5,10,20,50,100,200,500,1000,2000$的金币，要用最多的个数表示给定的$p$，问最多个数是多少。

解题思路

反向思考，求一下表示$sum-p$最小的个数。可以贪心的从上到下求解，对于每一种金币，每次选的个数必然是$max$或$max-1$（$max$代表到当前状态选这种金币最多能选的个数），否则显然不优（更低价值的金币必然能够被更高价值金币表示）。

AC代码 - by Mogg

复制

#include <algorithm>
#include<iostream>

using namespace std;
typedef long long ll;
const int ms = 10 * 2;
const int inf = 0x3f3f3f3f;
int f[ms], a[ms];
int n, res;
void dfs(int x, int val, int m)
{
    if (x == -1)
    {
        if (val == 0)
        {
            res = min(m, res);
        }
        return;
    }
    int tmp = min(f[x], val / a[x]);
    dfs(x - 1, val - tmp * a[x], m + tmp);
    if (tmp > 0)
    {
        tmp--;
        dfs(x - 1, val - tmp * a[x], m + tmp);
    }
}
int main()
{
    a[0] = 1;
    a[1] = 5;
    a[2] = 10;
    a[3] = 20;
    a[4] = 50;
    a[5] = 100;
    a[6] = 200;
    a[7] = 500;
    a[8] = 1000;
    a[9] = 2000;
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        int sum = 0;
        int cnt = 0; res = inf;
        for (int i = 0; i < 10; ++i)
        {
            scanf("%d", &f[i]);
            sum += a[i] * f[i];
            cnt += f[i];
        }

        if (sum < n)
        {
            res = -1;
        }
        else if (sum == n)
        {
            res = cnt;
        }
        else
        {
            dfs(9, sum - n, 0);
            if (res != inf)
                res = cnt - res;
            else
                res = -1;
        }

        printf("%d\n", res);
    }
    return 0;
}

B Count a × b

题目描述

定义$f(m)$为满足$0\leq i\leq m-1,0\leq j\leq m-1,i\times j\space mod \space m\neq 0$的二元组$(i,j)$个数。

求$g(n)=\sum_{m|n}f(m)$。

解题思路

求$ij\space mod\space m\neq 0$的个数可转化为求$m|ij$的个数，即求原表格中$0$的个数：

$f(m)=m^2-\sum_{i=0}^{m-1}\sum_{j=0}^{m-1}[m|ij]$

显然，求和符号从$0$到$m-1$和从$1$到$m$是等价的。于是考虑$[1,m]\times [1,m]$的表格，对于第$i$行，满足$m|ij$的$j$可以从$\frac mg,2\frac mg,…,g\frac mg$中取得，其中$g=gcd(m,i)$。也即，对于每个$gcd(m,i)=g$的$i$，对二元组$(i,j)$的贡献均为$g$。

枚举$m$的因子$g$，对于每个$g$，满足条件（$gcd(m,i)=g,1\leq i\leq m$）的$i$的个数为$\phi(\frac mg)$，其中$\phi(x)$为欧拉函数，表示$<x$且与$x$互质的数的个数（证明：$gcd(m,i)=g,gcd(\frac mg,\frac ig)=1$，对于每一个与$\frac mg$互质且小于$\frac mg$的数$x$，有$i=xg\leq m$）。于是式子转化为：

$f(m)=m^2-\sum_{g|m}g\times \phi(\frac mg)=m^2-\sum_{xy=m}x\phi(y)$

于是$g(n)=\sum_{m|n}(m^2-\sum_{xy=m}x\phi(y))=\sum_{m|n}m^2-\sum_{xy|n}x\phi(y)$

对于前半部分，每个$1e9$以内的数的因数个数$\leq 1344$，因此可以直接暴力枚举因数求解；也可质因数分解后变为$\prod (1+p_i^2+p_i^4+…+p_i^{2k_i})$的形式再预处理解决。

对于后半部分，枚举$x,y$，变为$\sum_{x|n}x\sum_{y|\frac nx}\phi(y)$。而欧拉函数和$e=[n=1]$的狄利克雷卷积为$id$，故$\sum_{d|n}\phi(d)=n$，即原式$=\sum_{x|n}x\frac nx=\sum_{x|n} n$。暴力枚举因数即可。

AC代码

复制

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define NN 100000
#define N (NN+10)
int np[N],cnt;
ll phi[N],p[N];
void sieve(){
    int i,j;np[0]=np[1]=1;
    for(i=2;i<N;i++){
        if(!np[i])p[cnt++]=i,phi[i]=i-1;
        for(j=0;j<cnt;j++){
            if(p[j]*i>=N)break;
            np[i*p[j]]=1;
            if(i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }else phi[i*p[j]]=phi[i]*phi[j];
        }
    }
}
unsigned long long pw[N][35];
void init(){
    int i,j;
    for(i=0;i<cnt;i++)pw[i][0]=1;
    for(i=0;i<cnt;i++)
        for(j=1;j<35;j++)
            pw[i][j]=pw[i][j-1]*p[i]*p[i];
    for(i=0;i<cnt;i++)
        for(j=1;j<35;j++)
            pw[i][j]+=pw[i][j-1];
}
int main(){
    int t,i,n;
    scanf("%d",&t);
    sieve();
    init();
    while(t--){
        scanf("%d",&n);
        unsigned long long tmp=n;
        vector<pair<int,int>>fac;
        for(i=0;i<cnt;i++){
            if(tmp%p[i]==0){
                int num=0;
                while(tmp%p[i]==0)num++,tmp/=p[i];
                fac.push_back(make_pair(i,num));
            }
        }
        unsigned long long now=1;
        if(tmp>1)now=tmp*tmp+1;
        for(auto i:fac)now*=pw[i.first][i.second];
        unsigned long long now2=n;
        if(tmp>1)now2=now2*2;
        for(auto i:fac)now2=now2*(i.second+1);
        now2=(1ull<<64)-now2;
        printf("%llu\n",now+now2);
    }
    return 0;
}

C Play a game

题目描述

给一个字符串$s$和一个字符串集合$T$，在$s$上给定的多组区间上玩游戏，每个人可以取走一个开头的元素或结尾的元素，到达空串或$T$中任意一个串的时候，游戏立即结束，下一手要操作的玩家失败，另一方获胜。问都采取最优策略的情况下谁能胜利。

解题思路

$f[i][j]$ 表示当前$[i,j]$区间先手必败还是必胜，先手必败当且仅当$[i,j]$是终止状态或$[i,j-1][i+1,j]$均为必胜状态，先手必胜当且仅当$[i+1,j][i,j-1]$至少有一个是先手必败状态。故$f[i][j]=!(f[i][j-1]\&f[i+1][j])$。

问题转化成了区间$dp$，用$AC$自动机跑出终止状态对应的位置，再进行区间$dp$即可。

但是这样的复杂度太高，会获得$TLE$。

考虑使用$bitset$对区间$dp$进行优化。改变$f[i][j]$的含义，变为当前区间长度为$i$，起始位置为$j$的必胜必败状态。于是有f[i][j]=~(f[i-1][j]&f[i-1][j+1])​， 即f[i]=~(f[i-1]&(f[i-1]>>1))​。复杂度$O(\frac{n^2}{64})$，可以勉强卡过。

AC代码

复制

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 80010
//int f[N][N];
bitset<N>f[N];
char a[N],s[N];
vector<int>pos[N];
struct ACAM{
    int tr[N][26],tot;
    int fail[N],pre[N],num[N],now;
    queue<int>Q;
    void init(){
        tot=0;
        num[0]=fail[0]=pre[0]=0;
        memset(tr[0],0,sizeof(tr[0]));
    }
    void insert(char s[]){
        int i;
        now=0;
        for(i=0;s[i];i++){
            int p=s[i]-'a';
            if(!tr[now][p]){
                tr[now][p]=++tot;
                num[tot]=fail[tot]=pre[tot]=0;
                memset(tr[tot],0,sizeof(tr[tot]));
            }
            now=tr[now][p];
        }
        num[now]=i;
    }
    void build(){
        int i;
        for(i=0;i<26;i++)if(tr[0][i])Q.push(tr[0][i]);
        while(!Q.empty()){
            int p=Q.front();Q.pop();
            for(i=0;i<26;i++){
                if(tr[p][i]){
                    fail[tr[p][i]]=tr[fail[p]][i];
                    Q.push(tr[p][i]);
                    pre[tr[p][i]]=num[fail[tr[p][i]]]?fail[tr[p][i]]:pre[fail[tr[p][i]]];
                }
                else tr[p][i]=tr[fail[p]][i];
            }
        }
    }
    void solve(char a[]){
        int i,now=0;
        for(i=0;a[i];i++){
            now=tr[now][a[i]-'a'];
            int temp=now;
            while(temp){
                if(num[temp])pos[num[temp]].push_back(i-num[temp]+2);
                temp=pre[temp];
            }
        }
    }
}T;
int main(){
    int i,t,n,m,q;
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
//	double time=clock();
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&q);
        scanf("%s",a);
        T.init();
        for(i=0;i<=n;i++)pos[i].clear();
        for(i=0;i<m;i++){
            scanf("%s",s);
            T.insert(s);
        }
        T.build();
        T.solve(a);
        f[0].reset();
        for(i=1;i<=n;i++){
            f[i]=~(f[i-1]&(f[i-1]>>1));
            for(auto j:pos[i])f[i][j]=0;
        }
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%d\n",(int)f[r-l+1][l]);
        }
    }
//	printf("%.5f\n",clock()-time);
    return 0;
}

D Pipes selection

题目描述

解题思路

AC代码

复制

E Rebuild

题目描述

给定$n$个点组成的多边形，要求以每个点为圆心画圆，相邻两个点之间的圆相切，求最大圆面积之和。

解题思路

任意找一个点作为起始点，设这个点对应半径$r_1$，那么有$r_2=d_{12}-r_1,r_3=d_{23}-r_2,…,r_1=d_{n1}-r_n$

这是一个$n$元$1$次方程组，我们将它化为矩阵，以$4$为例：

$\left(\begin{aligned}1\space1\space0\space 0\\ 0\space 1\space 1\space 0 \\ 0\space0\space1\space1\\ 1\space0\space0\space1\end{aligned}\right)\left(\begin{aligned}r_1\\ r_2\\ r_3\\ r_4\end{aligned}\right)=\left(\begin{aligned}d_{12}\\ d_{23}\\ d_{34}\\ d_{41}\end{aligned}\right)$

化简这个矩阵，当$n$为偶数时矩阵的秩为$n-1$，方程无解或有无穷多组解，解出$r_1$范围后问题转化成一个一元二次方程；$n$为奇数时秩为$n$，方程有唯一解。

AC代码 - by qxforever

复制

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+23;
int T,n;
int a[maxn],b[maxn];
double dis[maxn];
double ans[maxn];
const double eps = 1e-8;
const double pi = acos(-1.0);
bool eq(double a,double b)
{
    if(abs(a-b)<eps) return true;
    return false;
}

double getd(int i,int j)
{
    double aa=a[i],bb=b[i];
    double cc=a[j],dd=b[j];
    return sqrt((aa-cc)*(aa-cc)+(bb-dd)*(bb-dd));
}

bool check()
{
    ans[0]=1;
    for(int i=1;i<=n;i++){
        ans[i]=dis[i-1]-ans[i-1];
    }
    return eq(ans[0],ans[n]);
}


int main()
{
    cin >> T ;
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d%d",a+i,b+i);
        a[n]=a[0],b[n]=b[0];
        double sumd=0;
        for(int i=0;i<n;i++){
            dis[i]=getd(i,i+1);
            sumd+=dis[i];
        }
        if(n%2==0){
            //for(int i=0;i<n;i++) printf("%.2f ",dis[i]);
            if(!check()) {printf("IMPOSSIBLE\n");continue;}
            double d=0,kl,kr,pred=0;
            kl=0,kr=dis[0];
            for(int i=1;i<=n;i++){
                pred=dis[i-1]-pred;
                if(i%2){
                    kr=min(kr,pred);
                }
                else{
                    kl=max(kl,-pred);
                }
            }
            //printf("kk: %.2f %.2f\n",kl,kr);
            if(kl>kr+eps) {printf("IMPOSSIBLE\n");continue;}
            for(int i=0;i<n-1;i++){
                int t=1;
                if(i%2==0) t=-1;
                d+=1.0*t*(n-i-1)*dis[i];
            }
            d*=2;
            ans[0]=d/(-2*n);
            if(ans[0]<kl) ans[0]=kl;
            else if(ans[0]>kr) ans[0]=kr;
            sumd=ans[0]*ans[0];
            for(int i=1;i<n;i++){
                ans[i]=dis[i-1]-ans[i-1];
                sumd+=ans[i]*ans[i];
            }
            printf("%.2f\n",pi*sumd);
            for(int i=0;i<n;i++) printf("%.2f\n",ans[i]);
        }
        else{
            sumd/=2;
            bool can=true;
            int t=n/2;
            for(int i=0;i<n;i++){
                ans[i]=sumd;
                for(int j=0;j<t;j++){
                    int now=(i+1+2*j)%n;
                    ans[i]-=dis[now];
                }
                if(ans[i]<0) can=false;
            }
            if(can){
                double sum=0;
                for(int i=0;i<n;i++) sum+=ans[i]*ans[i];
                printf("%.2f\n",sum*pi);
                for(int i=0;i<n;i++) printf("%.2f\n",ans[i]);
            }
            else{
                printf("IMPOSSIBLE\n");
            }
        }
    }
}

F Almost Sorted Array

题目描述

问一个数列能否删掉某个数使得最终序列有序。

解题思路

升序降序讨论一番贪心删除就可以了。

AC代码 - by qxforever

复制

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+23;
int T,n;
int a[maxn];

int main()
{
    cin >> T;
    while(T--){
        scanf("%d",&n);
        bool can=true;
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
        }
        int mx=-1,cnt=0;
        for(int i=1;i<=n;i++){
            if(a[i]>=mx){
                mx=a[i];
                continue;
            }
            else{
                if(cnt==0){
                    if(a[i]>=a[i-2]){
                        mx=a[i];
                        cnt++;
                    }
                    else{
                        cnt++;
                    }
                }
                else{
                    can=false;break;
                }
            }
        }
        reverse(a+1,a+n+1);
        bool can2=true;
        mx=-1,cnt=0;
        for(int i=1;i<=n;i++){
            if(a[i]>=mx){
                mx=a[i];
                continue;
            }
            else{
                if(cnt==0){
                    if(a[i]>=a[i-2]){
                        mx=a[i];
                        cnt++;
                    }
                    else{
                        cnt++;
                    }
                }
                else{
                    can2=false;break;
                }
            }
        }
        if(can2||can){
            printf("YES\n");
        }
        else printf("NO\n");
    }
}

G Dancing Stars on Me

题目描述

整数格上给$n$个点，问是不是正多边形。

解题思路

直接判断正方形即可。

AC代码

复制

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
double basx,basy;
struct Point{
    int x,y;
}a[110];
Point operator-(Point a,Point b){
    return (Point){a.x-b.x,a.y-b.y};
}
int dot(Point a,Point b){
    return a.x*b.x+a.y*b.y;
}
int dis2(Point a,Point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int check(int i,int j,int k,int l){
    if(fabs(dot(a[j]-a[i],a[l]-a[i]))>1e-8)return 0;
    if(fabs(dot(a[i]-a[j],a[k]-a[j]))>1e-8)return 0;
    if(fabs(dot(a[l]-a[k],a[j]-a[k]))>1e-8)return 0;
    if(fabs(dot(a[k]-a[l],a[i]-a[l]))>1e-8)return 0;
    int ds=dis2(a[i],a[j]);
    if(ds==dis2(a[j],a[k])&&ds==dis2(a[k],a[l])&&ds==dis2(a[l],a[i]))return 1;
    else return 0;
}
int main(){
    int i,j,k,l,t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=0;i<n;i++)scanf("%d%d",&a[i].x,&a[i].y);
        if(n!=4){
            printf("NO\n");
            continue;
        }
        int flag=0;
        for(i=0;i<4;i++){
            for(j=0;j<4;j++){
                for(k=0;k<4;k++){
                    for(l=0;l<4;l++){
                        if(i!=j&&j!=k&&k!=l&&i!=k&&i!=l&&j!=l){
                            if(check(i,j,k,l))flag=1;
                        }
                    }
                }
            }
        }
        if(flag)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

H Partial Tree

题目描述

给一个函数$f$，让你建一棵树，它的度序列为$d_i$，最大化$\sum_{i=1}^{n}f(d_i)$。

解题思路

先对每一个点连一个度，还剩下$n-2$个度没有被使用，$f[i][j]$记录现在到了第$i$个$f$，用掉了$j$个度的$f$ 的总和最大值。这是一个完全背包问题。

AC代码

复制

#include <algorithm>
#include<iostream>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;
typedef long long ll;
const int ms = 2020 * 2;
const int inf = 0x3f3f3f3f;
int f[ms], dp[ms];
int n, m, res, mx;
void solve()
{
    mx = n - 2;
    for (int i = 0; i <= mx; i++) dp[i] = -inf;
    dp[0] = 0;
    for (int i = 1; i < n; i++)
    {
        for (int j = i; j <= mx; j++)
        {
            if (dp[j - i] != -inf)
                dp[j] = max(dp[j], dp[j - i] + f[i]);
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n - 1; ++i)
        {
            scanf("%d", &f[i]);
        }
        for (int i = 1; i < n - 1; ++i)
        {
            f[i] -= f[0];
        }
        if (n > 2)
        {
            solve();
            printf("%d\n", dp[mx] + n * f[0]);
        }
        else
        {
            printf("%d\n", n * f[0]);
        }
    }
    return 0;
}

I Chess Puzzle

题目描述

解题思路

AC代码

复制

J Chip Factory

题目描述

给定一个数列，求$max(a_i+a_j)\oplus(a_k)$。

解题思路

暴力即可。复杂度$O(\frac 12n^3)$。

也可以将所有元素加入一棵$trie$，再枚举$i,j$进行判断，复杂度$O(n^2\log max)$，常数挺大。

AC代码

复制

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[1010];
int main(){
    int i,j,k,T,n;
    scanf("%d",&T);
    while(T--){
        int ans=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)scanf("%d",&a[i]);
        for(i=0;i<n;i++){
            for(j=i+1;j<n;j++){
                for(k=j+1;k<n;k++){
                    ans=max(ans,(a[i]+a[j])^a[k]);
                    ans=max(ans,(a[k]+a[j])^a[i]);
                    ans=max(ans,(a[i]+a[k])^a[j]);
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

K Maximum Spanning Forest

题目描述

解题思路

AC代码

复制

L House Building

题目描述

有一堆立方体积木，给定一个积木高度，求露在外面的表面积。

解题思路

暴力枚举每一层即可。

AC代码 - by Mogg

复制

#include <algorithm>
#include<iostream>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;
typedef long long ll;
const int ms = 55;

int c[ms][ms];
int n, m, res, mx;
void solve(int x)
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (c[i][j] >= x)
            {
                if (c[i + 1][j] >= x) res--;
                if (c[i - 1][j] >= x) res--;
                if (c[i][j + 1] >= x) res--;
                if (c[i][j - 1] >= x) res--;
            }
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d", &n, &m); res = 0, mx = 0;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                scanf("%d", &c[i][j]);
                if (c[i][j])
                {
                    res++;
                    res += 4 * c[i][j];
                    mx = max(c[i][j], mx);
                }
                c[i][m + 1] = 0;
                c[n + 1][j] = 0;
            }
        }
        for (int i = 1; i <= mx; ++i)
        {
            solve(i);
        }
        printf("%d\n", res);
    }
    return 0;
}

M Security Corporation

题目描述

解题思路

AC代码

复制