牛客（NC）广西大学第三届程序设计竞赛（同步赛）部分题解
赛题链接：牛客（NC）广西大学第三届程序设计竞赛（同步赛） 点击传送
几个简单题，大佬勿喷，有错误欢迎指出啊（这是直接从我csdn上copy来的）
A题 A++++++++++++++++++（签到题）
签到题，给n个字符串，其中national和international为一组，求其中有多少组；
数据小直接暴力没啥好说的
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
int t;
scanf("%d",&t);
int n;
string s
while(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<bits/stdc++.h>
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<bits/stdc++.h>
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<bits/stdc++.h>
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;
} 好了，小菜鸡的我只会这些题目，题解有问题欢迎各位大佬指正(≧∇≦)ﾉ
京公网安备 11010502036488号