A-Don't Starve

来源: 牛客多校训练营5 算法: 动态规划补完: Yes 完成时间: August 11, 2022

题解

二维平面上有\(n≤2000\)个点会刷新食物, 威尔逊从原点出发收集食物, 每次前往下一个食物的距离要比上一次短, 每个食物被收集过后会重新刷新, 求最多可以收集到的食物数量.

每两个点之间都可以走, 记录每条边的信息, 第\(i\)条边有起点\(s_i\), 终点\(t_i\), 长度\(l_i\).

从原点出发故除了食物之间的边, 还要再考虑从原点到食物的边.

考虑\(dp_i\)表示上一步走了第\(i\)条边的最大收集量, 从\(s_i\)走到了\(t_i\).

则下一步\(dp_j\)走第\(j\)条边需要从\(t_i\)出发, 即\(t_i=s_j\), 走的长度要变短, 即\(l_j<l_i\)

\[ dp_i=1+\max\{dp_j|s_j=t_i, l_j<l_i\} \]

从最长的边开始依个枚举, 每次\(dp\)以上一次数据更新, 使用滚动数组.

代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2005;

struct Side {
    int s, t;
    double l;
    friend bool operator<(const Side &Left, const Side &Right) {
        return Left.l > Right.l;
    }
};

vector<Side> sides;
int x[MAXN], y[MAXN];

double lengthOf(double dx, double dy) {
    return sqrt(dx*dx+dy*dy);
}

int main() {
    int n;
    cin>>n;
    for (int i = 1; i <= n; i++) 
        cin>>x[i]>>y[i];
    for (int i = 0; i <= n; i++) 
        for (int j = 1; j <= n; j++) 
            if (i!=j)
                sides.push_back({i,j,lengthOf(x[i]-x[j],y[i]-y[j])});
    sort(sides.begin(),sides.end());
    vector<int> f(n+1,-0x3f3f3f3f), g(n+1,-0x3f3f3f3f);
    f[0] = 0;
    for (int i = 0, j = 0; i < sides.size();i = j) {
        vector<Side>t;
        for (j = i; j < sides.size() && sides[i].l == sides[j].l; j++)
            t.push_back(sides[j]);
        for (auto e : t)g[e.t] = -0x3f3f3f3f;
        for (auto e : t)g[e.t] = max(g[e.t], f[e.s] + 1);
        for (auto e : t)f[e.t] = max(f[e.t], g[e.t]);
    }
    cout << *max_element(f.begin(), f.end()) << endl;
    return 0;
}

B-Watches

来源: 牛客多校训练营5 算法: 二分题目链接: https://ac.nowcoder.com/acm/contest/33190/B 补完: Yes 完成时间: August 1, 2022

题意概括

NIO要向制造产进一批手表，需要花费的金额除了手表本身的价钱外还有税收，计算方法为如果他买了k个手表，第i个手表的价格就是手表原价+k*i，现在NIO有M美元，问NIO最多可以买多少手表？

解题思路

采用二分的方法，求出NIO最多可以买到多少手表。

1）用结构体存储手表的原价、位置以及最终价格，输入原价时即记下该手表的位置i；

2）最少NIO的钱可能一个手表都不购买，最多可能购买n个，因此把0和n传入二分函数中，如果二分结果（买的手表个数）满足条件，则寻找更大的数判断是否满足条件。

3）判断是否满足条件的方法为：判断函数传入手表个数k，在购买k个手表的条件下，计算每个手表的最终价格，用sort从小到大排序，选择k个价格低的累加，计算购买k个所需的总价，如果小于或等于M，则满足条件，否则不满足。

注意：总价和手表的最终价格要用long long！！

代码

#include <iostream>
#include<algorithm>
using namespace std;
int n,m;
struct watch{
    long long w; 
    int a;
    int i;
}A[1000005];

bool cmp(watch x,watch y){
	return x.w<y.w;
}

int check(int k)
{
	long long res=0;
	for(int i=1;i<=n;i++){
		A[i].w=A[i].a+k*A[i].i;  //计算手表的最终价格
	}
	sort(A+1,A+n+1,cmp);
	for(int i=1;i<=k;i++){
		res+=A[i].w;
	}
	return res<=m;  //判断这个mid是不是符合题目条件（是否为1）;
}

int find(int min,int max) 
{
	int ans=-1;
	while (min<=max)
	{
		int mid=(min+max)/2;
		if(check(mid))
		{
			ans=mid;
			min=mid+1;  //依题目的临界条件而变，此题为寻找满足条件的最大数
		}
		else max=mid-1;  //依题目的临界条件而变
	}
	return ans;
}

int main(){
	cin>>n>>m;
	int i;
	for(i=1;i<=n;i++)
	{
		cin>>A[i].a;
		A[i].i=i;	    //记录手表位置
	}
	cout<<find(0,n);
	return 0;
}

C-Bit Transmission

来源: 牛客多校训练营5 算法: 模拟题目链接: https://ac.nowcoder.com/acm/contest/33190/C 补完: Yes 完成时间: August 23, 2022

题目链接

题意简述

有一个01串，\(3N\)次询问，每次询问一个索引（从0开始），机器会返回这个索引位置的字符是不是1。

如果机器只最多给一个错误回答，是否能得到唯一的串？能，输出串，不能，输出-1。

AC代码

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n==3)cout<<"111";
    else cout<<"-1";
    return 0;
}

~~开玩笑的，这不是正解。但这真的是AC代码。~~

题目分析

首先，”机器最多给一个错误回答“是前提。

~~虽然在题目修锅之前样例没保证这个还得把和前提冲突的情况考虑进去。~~

~~多考虑点情况的代码可以通过现在的样例。~~

那么答复一定不会出现多组冲突（比如0索引报告过YES和NO，1索引也报告过YES和NO）或者一组里面多个冲突（比如0索引报告了3个YES和4个NO）的情况。

也就是答案可能是完全不冲突（所有索引都只报告YES或者NO），或者只存在一组冲突的情况。

并且存在冲突的那种情况中，错误答案只报告了一次。

那正确答案就很好组成了，不冲突的索引就是报告了非0次的那个答案，冲突的索引就是报告了多次的那个答案。可以统一写成出现次数多的那个答案。

无法判断的情况也很显然：

①该索引没有被报告。完全无法掌握对应索引的信息。

②冲突报告的索引，YES和NO各被汇报了一次。无法确定哪个是假信息。

③所有报告不存在冲突。但有索引只有一个报告。不管是YES还是NO，无法确定这条信息是否是真信息。（因为找不到那个可能存在的假信息在哪）

其中①和②是YES和NO都被报告了0次或1次，可以合并成两个次数相等来判断。

判断前事先统计每个索引的01结果报告数量即可。（YES表示这里是1，NO表示这里是0）

代码见完整代码。

————

顺便考虑一下题目”机器最多给一个错误回答“不保证的情况。

也就是出现机器给出多个错误答案直接输出-1的考虑。

那么也就是加上前面认为不会出现的两种情况：

①存在多个冲突对。

②一组冲突里两种结果都有多次报告。

代码见特殊版。

完整代码

#include<iostream>
using namespace std;
int cnt[100010][2]={0};
int main(){
    int n;
    cin>>n;
    for(int i=0;i<3*n;i++){
        int id;
        string IF;
        cin>>id>>IF;
        if(IF[0]=='N')cnt[id][0]++;
        else cnt[id][1]++;
    }
    string ans="";
    int flag=0;
    for(int i=0;i<n;i++){
        ans+=cnt[i][1]>cnt[i][0]?'1':'0';//存结果串
        if(cnt[i][1]!=0&&cnt[i][0]!=0){
            flag=1;//标记存在冲突
        }
        if(cnt[i][1]==cnt[i][0]){//均0次或者均1次
            cout<<"-1";
            return 0;
        }
    }
    if(flag==0){//不存在冲突
        for(int i=0;i<n;i++){
            if(cnt[i][0]+cnt[i][1]==1){//但有索引只有一个报告
                cout<<"-1"; 
                return 0;
            }
        }
    }
    cout<<ans;
    return 0;
}

完整代码-特殊版

#include<iostream>
using namespace std;
int cnt[100010][2]={0};
int main(){
    int n;
    cin>>n;
    for(int i=0;i<3*n;i++){
        int id;
        string IF;
        cin>>id>>IF;
        if(IF[0]=='N')cnt[id][0]++;
        else cnt[id][1]++;
    }
    string ans="";
    int flag=0;
    for(int i=0;i<n;i++){
        ans+=cnt[i][1]>cnt[i][0]?'1':'0';
        if(cnt[i][1]!=0&&cnt[i][0]!=0){
            if(flag){
						//冲突存在标记的另一个使用处：出现第二个冲突。
                cout<<"-1";
                return 0;
            }
            flag=1;
        }
        if(cnt[i][1]==cnt[i][0]){
            cout<<"-1";
            return 0;
        }
        if(cnt[i][1]>=2&&cnt[i][0]>=2){
						//一组冲突多个报告的情况
            cout<<"-1";
            return 0;
        }
    }
    if(flag==0){
        for(int i=0;i<n;i++){
            if(cnt[i][0]+cnt[i][1]==1){
                cout<<"-1"; 
                return 0;
            }
        }
    }
    cout<<ans;
    return 0;
}

D-Birds in the tree

来源: 牛客多校训练营5 算法: DFS, 动态规划, 树形DP 题目链接: https://ac.nowcoder.com/acm/contest/33190/D 补完: Yes 完成时间: August 11, 2022

题解

给有\(n\)个节点的树, 每个节点具有颜色\(0\)或颜色\(1\). 求其有多少联通子图, 满足度数为\(1\)的节点颜色相同.

树上求方案树考虑树形DP

设\(dp_{u,c}\)为在以\(x\)为根的子树内, 有多少包含\(u\)的连通子图, 叶结点(不包括\(u\))的颜色为\(c\)的方案数.

对一个父节点\(u\)的某一个子节点\(v_i\)的方案数都有选和不选两种情况, 故共有\(dp[v_i][c]+1\)种方案.

对一个父节点\(u\)的所有个子节点\(v_i\), 每个子节点的方案数都可以独立选取, 故父节点的方案数为所有子节点方案数的乘积.

\[ dp'[u][c]=\prod_v(1+dp[v][c]) \]

当\(u\)不选取的任何子树数时, \(u\)本身也是一个叶结点, 考虑\(u\)的颜色, 若此时其颜色不为\(c\)则为无效方案数, 需要减去.

\[ dp[u][c]=\prod_v(1+dp[v][c])-(a[u]!=c) \]

统计答案时统计各个结点的方案数, 另外考虑当一个结点仅选取一个子树时, \(u\)本身也是一个叶结点, 考虑\(u\)的颜色, 若此时其颜色不为\(c\)则为无效方案数, 需要减去.

\[ ans_c=\sum_u\left(dp[u][c]-(a[u]!=c)\sum dp[v][c]\right) \]

最后加和答案即可

\[ Ans=ans_0+ans_1 \]

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll P = 1000000007;
const int MAXN = 300005;

int n;
char a[MAXN];
ll Ans = 0;
vector<int> e[MAXN];
ll dp[MAXN][2];

ll add(ll a, ll b) {
    return (a+b+P)%P;
}
ll mul(ll a, ll b) {
    return (a*b)%P;
}

void dfs(int u, int f, int c) {
    ll prod = 1, sum = 0;
    for (auto v: e[u]) {
        if (v==f)continue;
        dfs(v,u,c);
        prod = mul(prod, 1+dp[v][c]);
        sum  = add(sum ,   dp[v][c]);
    }
    dp[u][c] = add(prod, -(a[u]!=c));
    Ans = add(Ans, dp[u][c]-(a[u]!=c)*sum);
}

void solve() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        char c; 
        cin>>c;
        a[i] = c - '0';
    }
    for (int i = 1; i < n; i++) {
        int x, y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1,0,0);
    dfs(1,0,1);
    cout<<Ans;
}

int main() {
    int T = 1;
    // cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

F-A Stack of CDs

来源: 牛客多校训练营5 算法: 计算几何题目链接: https://ac.nowcoder.com/acm/contest/33190/F 补完: Yes 完成时间: August 2, 2022

题解

有\(n\)张CD叠在平面上, 求可见的CD弧长(不是求总的投影的边缘长).

后放置的圆会压到先放置的圆, 将先放置的圆的部分弧压住看不到.

以样例为例:

放置第一圆, 在最底下.

放置第二圆, 此时小圆没有压到任何弧. 也没有被压它自身是可见的.

放置第三圆, 此时第二圆完全被第三圆覆盖, 标红表示不可见.

同时第一圆的右上角有部分弧被第三圆覆盖, 标红表示不可见.

发现后放置的圆有可能对先放置的圆有影响, 会将其完全覆盖, 或者覆盖部分弧长.

为求剩余可见弧长, 可以记录此圆是否被完全覆盖, 若为被完全覆盖则记录被覆盖了多少弧长. 最后从周长中减去被覆盖的弧长即为可见弧长. 统计所有圆的可见弧长即为答案.

由于后续可能有多个圆对它覆盖, 这些弧之间可能有重叠, 所以不能单纯记录被覆盖弧长的长度, 而是要记录被覆盖弧长的起始点, 最后区间合并统计被覆盖弧长的总长度. 记录圆上起始点可以使用极角.

先用余弦定理求弧长圆心角的绝对值

\[ \cos \alpha=\frac{dist^2+a.r^2-b.r^2}{2*a.r*dist} \]

\[ \alpha=\arccos \frac{dist^2+a.r^2-b.r^2}{2*a.r*dist} \]

再通过正切求出圆心角相对极轴的偏移量

\[ \tan\beta=\frac{y_b-y_a}{x_b-x_a} \]

\[ \beta=\arctan\frac{y_b-y_a}{x_b-x_a} \]

相加之后可得一条弧的起始点极角

这样处理后的极角可能落在\([-2\pi,2\pi]\)区间内, 而一个圆的正确区间是\([0,2\pi]\), 可以通过让负数直接\(+2\pi\)落回正确区间.

如果被覆盖弧越过零点, 应该拆成两段处理.

代码

#include<bits/stdc++.h>
#define ll long long
#define PI M_PI
using namespace std;
const int MAXN = 1005;
struct arc{
    double start;
    double end;
};
bool cmp(arc a,arc b){
    return a.start<b.start || (a.start==b.start&&a.end>b.end);
}
struct circle{
    double x;
    double y;
    double radius;
    vector<arc> covered;
    bool alive = true;
}Circle[MAXN];
double sqr(double x){
	return x*x;
}
void analyseCoverWith(circle &a,circle b){
    if(!a.alive)return ;
    double deltax = b.x-a.x;
    double deltay = b.y-a.y;
    double dis = sqrt(sqr(deltax)+sqr(deltay));
    if(dis>=a.radius+b.radius)                 return; //外离外切
    if(dis+b.radius<=a.radius)                 return; //上者小无覆盖
    if(dis+a.radius<=b.radius){a.alive = false;return;}//上者大全覆盖
    double alpha = acos((sqr(a.radius)+sqr(dis)-sqr(b.radius))/(2*a.radius*dis));
    double beta  = atan2(deltay,deltax);
    double start = ((beta-alpha)>0)?(beta-alpha):(beta-alpha+2*PI);
    double end   = ((beta+alpha)>0)?(beta+alpha):(beta+alpha+2*PI);
    if(start<=end){
        a.covered.push_back({start, end});
    }
    else{
        a.covered.push_back({  0  , end});
        a.covered.push_back({start,2*PI});
    }
}
double aliveArcOf(circle a){
    if(!a.alive)return 0;
    Circle[i].covered.push_back({  0 ,  0 });
    Circle[i].covered.push_back({2*PI,2*PI});
    sort(a.covered.begin(),a.covered.end(),cmp);
    double lim = 0, temp = 0;
    for(auto arc: a.covered){
        if(arc.start>lim)
            temp+=arc.start-lim;
        lim = max(lim,arc.end);
    }
    return temp*a.radius;
}
void solve(){
    int n;
    double ans = 0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>Circle[i].x>>Circle[i].y>>Circle[i].radius;
    }
    for(int i = 1; i<=n; i++){
        for(int j = i+1; j<=n; j++){
            analyseCoverWith(Circle[i],Circle[j]);
        }
        ans += aliveArcOf(Circle[i]);
    }
    printf("%.15lf",ans);
}
int main(){
    int T = 1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

G-KFC Crazy Thursday

来源: 牛客多校训练营5 算法: 回文自动机, 字符串题目链接: https://ac.nowcoder.com/acm/contest/33190/G 补完: Yes 完成时间: August 3, 2022

题意

给定一个字符串，分别输出以’k‘、’f‘、’c‘结尾的回文子串个数。

解法

套用回文自动机模板，在字符串存入回文树的过程中加上一层判断：当遇到’k‘、’f‘、’c‘时，分别计算出以该字符结尾的回文串的个数，并记录累加结果

当字符串全部存入后，也就算出了所有以’k‘、’f‘、’c‘结尾的回文子串个数

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=500010;
char s[N];
int len[N],n,num[N],fail[N],last,cur,pos,trie[N][26],tot=1;
long long k,f,c;
int getfail(int x,int i)
{
	while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
	return x;
}
int main()
{ 
    cin>>n;
	  scanf("%s",s);
    fail[0]=1;len[1]=-1;
    for(int i=0;i<=n-1;i++){ 
    	pos=getfail(cur,i);
        //找到cur的fail链中能匹配i位的最长回文后缀
      if(!trie[pos][s[i]-'a']){
        	fail[++tot]=trie[getfail(fail[pos],i)][s[i]-'a'];
        	trie[pos][s[i]-'a']=tot;
        	len[tot]=len[pos]+2;
          num[tot]=num[fail[tot]]+1;
		   }//不存在建立点，存在直接走过去
       cur=trie[pos][s[i]-'a'];
       last=num[cur];
       if(s[i]=='k'){
	       	 k+=last;
	      }    
	     if(s[i]=='f'){
    	     f+=last;
        }
    	 if(s[i]=='c'){
	 	       c+=last;
	      }
	   }
    cout<<k<<' '<<f<<' '<<c; 
	  return 0;
}

H-Cutting Papers

来源: 牛客多校训练营5 算法: 计算几何题目链接: https://ac.nowcoder.com/acm/contest/33190/H 补完: Yes 完成时间: August 1, 2022

题解

当\(x>0\&\&y>0\)时, \(x+y+x+y≤n\), 即为\(x+y≤n/2\)

当\(x<0\&\&y<0\)时, \(x+y+x+y≥n\), 即为\(x+y≥n/2\)

当\(x>0\&\&y<0\)时, \(|x|+|y|+(|x|-|y|)≤n\), 即为\(|x|≤n/2\)

当\(x<0\&\&y>0\)时, \(|x|+|y|+(|y|-|x|)≤n\), 即为\(|y|≤n/2\)

对应六条边

半径为\(n/2\)的圆

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
    double n;
    cin>>n;
    double r = n/2;
    double ans = r*r*M_PI/2+r*r*2;
    printf("%.15lf",ans);
}
int main(){
    int T = 1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

K-Headpho

来源: 牛客多校训练营5 算法: 模拟题目链接: https://ac.nowcoder.com/acm/contest/33190/K 补完: Yes 完成时间: August 26, 2022

题意

NIO和妹妹拿耳机
共有\(n\)对耳机，妹妹已经拿了\(k\)对
剩下的耳机两人分，NIO一只一只拿
问剩下的耳机中NIO至少要拿多少只才能拥有比妹妹多对的耳机？

解法

NIO最少要拿到\(k+1\)对耳机，此时总的耳机对数就是\(k+k+1\)，若\(k+k+1>n\)，说明NIO拿不到\(k+1\)对，输出\(-1\)
因为NIO是一只一只拿的，所以NIO拿的比妹妹多的最坏情况就是，NIO拿了一半多一个，这样妹妹就凑不到一半的耳机了

代码

#include <iostream>
using namespace std;
int main(){
    int n,k,ans=0;
    cin>>n>>k;
    ans=k+1;
    if(ans+k>n){
        ans=-1;
    }else {
       ans=n+1;
    }
    cout<<ans;
    return 0;
}

Shelter

2022牛客多校训练营05