“中国东信杯”广西大学第三届程序设计竞赛（同步赛）水题题解（大佬勿喷）

牛客（NC）广西大学第三届程序设计竞赛（同步赛）

赛题链接：牛客（NC）广西大学第三届程序设计竞赛（同步赛） 点击传送

A题 A++++++++++++++++++（签到题）

签到题，给n个字符串，其中national和international为一组，求其中有多少组；
数据小直接暴力没啥好说的

#include
typedef long long ll;
using namespace std;int main()
{int t;scanf("%d",&t);int n;string swhile(t--){scanf("%d",&n);int ans=0,cnt=0;for(int i=0;i<n;i++){//记录输入的数据中有多少个national和international；cin>>s;//输入字符串s，可以用字符数组代替if(s=="national")ans++;else cnt++;}printf("A");for(int i=0;i<min(ans,cnt);i++)printf("+");//输出A后面的‘+’的个数为ans和cnt中最短的那个；printf("\n");}return 0;
}

B题 GDP Carry（博弈）

博弈：博弈是信息学和数学试题中常会出现的一种类型，算法灵活多变是其最大特点， 寻找必败态即为针对此类试题给出一种解题思路。

注：题解中Antinomy称为小A；

B题给出一个序列，小A每次从序列中取出一段非空连续的数（取走后剩余的序列视为连续），它们的和为奇数，小西每次从序列中取出一段非空连续数，和为偶数，小A先手，轮到谁无法操作即为输。

对于输入的序列，无论数值大小，都可以看作为一组01串（因为题目只看奇偶，奇数为1，偶数为0）；
对于每一种01串都可分为三种情况：
①1的数量为奇数个（即有奇数个奇数）
②1的数量为偶数个（即有偶数个奇数）
③序列中没有1（即为偶数序列）
对于情况①小A先手，取连续元素和为奇数的序列，可直接取完整个序列，小西无法进行操作，情况①小A必胜；

对于情况②小A先手，取连续元素和为奇数的序列，可取至序列仅剩一个奇数，此时若序列中还有偶数，小西取一个偶数序列（无法取完整个序列），之后小A可取完剩余的整个序列，小西无法操作，小A胜；若序列中没有其他偶数，小西无法操作，小A胜；情况②小A必胜

对于情况③，偶数序列，小A先手无法取数，小西必胜；情况③小西必胜

#include
typedef long long ll;
using namespace std;int main()
{int n;scanf("%d",&n);int ans=0,a;for(int i=0;i<n;i++){scanf("%d",&a);if(a%2!=0)ans++;}if(ans==0) printf("XiJam");else printf("Antinomy");return 0;
}

C题 Interpretability（思维题）

对于题意给出的这些边，求这些边最多能构成多少个三角形；
思维题，也可理解为一种贪心；

首先这题n的范围n较大，直接存边大小存不下；
关于这题的三角形构造，每条边都是2的整数次方（即2，4，8，16……），即三条长度不同的边无法构成三角形，腰比底小的也无法构成三角形；
构成三角形只有两种：1、等边三角形；2、等腰三角形（腰长比底长大）。

一开始我的想法是存边数，即存数组f，先对于每个fi，除以三取出所有的等边三角形，取完后%3取余数，此时f数组中只有0，1，2三种数字，之后，对于f数组从后往前遍历（因为腰要比底长），构造等腰三角形。先将数组中的2与在2前面的1组合，之后对于剩下的2，组合剩下的三角形；

	int n;scanf("%d",&n);long long ans=0;for(int i=1;i<=n;i++){scanf("%lld",&f[i]);ans+=f[i]/3;f[i]%=3;}long long x=0;for(int i=n;i>=1;i--){if(f[i]==2)x++;else if(f[i]==1&&x){ans++;if(x>0)x--;}}ans+=(x*2)/3;cout<<ans<<endl;return 0;

简单来说就是先贪心等边三角形，再组合等腰三角形；
但是这种思维是错误的；就很荣幸的WA了；
例如：对于样例：3 4 4 4；用上述方法得出3个三角形；若是先贪等腰三角形，可得4个三角形

AC思路：先贪等腰三角形；
对于f数组，从前往后遍历，f1无法构造等腰三角形，构造等边三角形，对于后面每个fi，若是前面有剩余的边给它当底边，构造等腰三角形，剩余的边构造等边三角形，再剩余的边做底边与后面的边构造；（这样都不用存数组）

#include
typedef long long ll;
using namespace std;int main()
{ll n;scanf("%lld",&n);ll a,t,ans=0;//t用来存前方有多少条边做底边,ans存构造多少个三角形，数据较大int会爆，用long long存for(int i=0;i<n;i++){scanf("%lld",&a);if(t!=0){//前面有边做底边，贪等腰int un=a/2;//对于每个底边要两条腰构造三角形if(un>=t){a-=2*t;ans+=t;t=0;}else{a-=2*un;ans+=un;t-=un;}}ans+=a/3;//剩余的构造等边三角形t+=a%3;}printf("%lld\n",ans);return 0;
}

E题 Antinomy与黑风海（图论模板题）

一看到这题，就想到了图论，仔细看求最少需要的时间，就想到了最小生成树和最短路，再看一眼，单向边，我就用最短路写了。

看一下数据范围1e6，普通的最短路算法存不下，就用堆优化的Dijkstra算法，
注：不熟悉Djk的可以看我的另一篇博客————>最短路径———Dijkstra算法（点击传送）

这题的难点是，每到一个点还要回到原点再到下一个点，开始的确有点懵（单向边），后来仔细想；
单向边，从s（默认为1）开始，我正着Djk一次，反着Djk一次，这两次不同的是把单向边的方向翻转，
得出的数据为s到其他点的最短距离和其他点到s的最短距离将两个dis数组加起来即为题目所求；

贴个代码：

#include
using namespace std;
#define INF 0x3f3f3f3f
struct lq{int x,d;
};struct xb{int x,d;bool operator <(const xb &a) const{return x>a.x;}
};priority_queue<xb> q;
int dis[1000005];
int ans[1000005];
vector<lq> a[1000005];
vector<lq> b[1000005];
void Djk(int n,int s){for(int i=1;i<=n;i++) dis[i]=INF;xb e;e.x=s;e.d=0;dis[s]=0;q.push(e);while(!q.empty()){e=q.top();q.pop();int v=e.x;int u=e.d;if(dis[v]<u) continue;int len=a[v].size();for(int i=0;i<len;i++){lq g=a[v][i];if(dis[v]+g.d<dis[g.x]){dis[g.x]=dis[v]+g.d;e.x=g.x;e.d=dis[g.x];q.push(e);}}}
}
void DJK(int n,int s){for(int i=1;i<=n;i++) ans[i]=INF;xb e;e.x=s;e.d=0;ans[s]=0;q.push(e);while(!q.empty()){e=q.top();q.pop();int v=e.x;int u=e.d;if(ans[v]<u) continue;int len=b[v].size();for(int i=0;i<len;i++){lq g=b[v][i];if(ans[v]+g.d<ans[g.x]){ans[g.x]=ans[v]+g.d;e.x=g.x;e.d=ans[g.x];q.push(e);}}}
}
int main()
{int n,m;scanf("%d%d",&n,&m);int x,y,z;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);lq e;e.x=y;e.d=z;a[x].push_back(e);e.x = x;b[y].push_back(e);}Djk(n,1);DJK(n,1);long long sum=0;for(int i=1;i<=n;i++){sum+=dis[i];sum+=ans[i];}printf("%lld",sum);return 0;
}

好了，小菜鸡的我只会这些题目，题解有问题欢迎各位大佬指正(≧∇≦)ﾉ

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！