河南理工大学算法协会暑期集训积分赛（三）
今天如期举行了第三场积分赛，没啥好说的，还是那句话
积分赛，被打爆的积分赛(music
蚂蚁觅食（一）
Description:
一只饥饿的小蚂蚁外出觅食，幸运的小蚂蚁发现了好多食物，但是它只有一次搬食物的机会。
可因为力气太小了，它不能搬走重量超过自己体重的食物,且只能搬走位置相邻的两个食物，或者只搬走其中一个。
食物的位置不会改变。
这可难住了这只蚂蚁，它不知道它最多能搬走多重的食物。请帮小蚂蚁计算。
输入格式
第一行一个正整数n，(n>=0并且n<=1000)
第二行n个正整数 A[1].....A[n]，A[i] 表示在第i 个位置上食物的重量。A[i]<=1e9.
第三行一个正整数m，表示蚂蚁的体重。(m<=1e9).
输出格式
一个整数表示小蚂蚁能带走的食物的重量。
样例
input
3
1 3 3
4
output
4
Problem solving:
神TM签到题，愣是没看懂是啥意思。。。
最后看懂了，就是找一个跟m尽量接近的一个数或者相邻两个数的和尽量接近m的。
我是把每个数和相邻的数的和存进一个数组然后O(N)查找
找到输出就行
Code:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2005;
long long a[maxn],m;
int main()
{
int n,ans=0;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=n;i<2*n-1;i++) a[i]=a[i-n]+a[i-n+1];
sort(a,a+2*n-1);
cin>>m;
for(int i=0;i<2*n-1;i++)
{
if(a[i]>m) break;
ans=a[i];
}
cout<<ans<<endl;
} Description:
一只饥饿的小蚂蚁外出觅食，幸运的的小蚂蚁发现了好多食物。
但是这些食物位于一个N∗M的方格魔法阵的右下角，而小蚂蚁位于方格法阵的左上角。
并且小蚂蚁被施展了魔法，它只能向下或者向右走。
请你帮助小蚂蚁计算一下，它一共有多少条路可以走到有食物的方格。
输入格式
多组输入，
每一组两个正整数N， M （N,M≤30）。表示一个方格魔法阵。
输出格式
一个整数表示一共有多少条路。
样例
input
2 3
output
3
Problem solving:
这道题据说可以用排列数做（高中知识。）
倒是我哪会高中知识啊，就推呗。
然后找到了递推式，我们用dp[x][y]来表示（x，y）位置到终点有几条路。那么可以得到dp[x][y]=dp[i-1][j]+dp[i][j-1]
边界条件是，当x或者y等于1的时候只有一条路，因为只能往右或者往下走。
推理过程：
首先看一下图吧
假设我们现在要求(4,3)这个位置到终点(1,1)的路径条数，从(4,3)走出来只有两种选择，向右或者向下，所以我们走到了(4,2),(3,3),这时我们只需要求(4,2)(3,3)到终点的路径条数然后求和就行了。以此类推，就可以得到上面的递推式了。
然后就是注意这个是多组输入。。！！！
Code:
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll ans[32][32];
int main()
{
for(int i=1;i<=31;i++)
{
for(int j=1;j<=31;j++)
{
if(i==1||j==1) ans[i][j]=1;
else ans[i][j]=ans[i-1][j]+ans[i][j-1];
}
}
ll n,m;
while(cin>>n>>m)
{
cout<<ans[n][m]<<endl;
}
}蚂蚁觅食（三）
Description:
马上就要冬天了，勤劳的小蚂蚁需要储存足够多的食物才能安全过冬。
今天，这只小蚂蚁走出巢穴寻找食物，但是这次蚁巢周围只有很少的食物，它需要去别的地方。
不幸的是小蚂蚁的体力很有限，而且每走一个单位长度就要消耗一点体力，不能找的时间太久，所以想让你帮忙计算一下它是否能用剩下的体力把足够多的食物搬回蚁巢。
由于蚂蚁的嘴太小，每次最多只能衔起一个食物。
输入格式
输入t组, t≤20
第一行三个数n,E,V表示食物的个数，蚂蚁剩余的体力，安全过冬需要的最少食物体积, 0<n≤100,0<E,V≤10000。
接下来n行，每行两个数pi,vi,表示第i个食物的位置和体积,0<p[i],v[i]≤1000。
初始蚂蚁和蚁巢均在坐标轴原点。
输出格式
每个输出占一行。
如果蚂蚁能安全过冬，输出 “YES”,否则输出”NO”。
样例
input
2
1 2 2
1 2
1 2 2
2 1
output
YES
NO
Problem solving:
一道简单的01背包题，背包容量是蚂蚁当前剩余的体力值。
每个物品的价值就是食物的体积，所占的背包容量的大小就是距离乘2（因为还要回来）。
然后比较最多能达到的食物体积，与需要的最少的食物体积进行标比较就行了。01背包的部分套板子写的
Code:
#include<bits/stdc++.h>
int n,e,v;
const int maxn=100005;
int si[maxn],jia[maxn],dp[100005];
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
cin>>n>>e>>v;
for(int i=0;i<n;i++)
{
cin>>si[i]>>jia[i];
si[i]*=2;
}
for(int i=0;i<n;i++)
{
for(int j=e;j>=si[i];j--)
{
dp[j]=max(dp[j],dp[j-si[i]]+jia[i]);
}
}
if(dp[e]>=v) puts("YES");
else puts("NO");
}
}蚂蚁平面
Description:
平面上有 n只蚂蚁，它走过的路径可以看作一条直线
由这n 条直线定义的某些区域是无界的，而另一些区域则是有界的。
有界区域的最大个数是多少？
比如现在有4条直线，只有下面最左边的图中直线定义的有界区域是最多的
输入格式
T 组输入, (1≤T≤100)
每组一个数 n ，(1≤n≤109)
输出格式
对于每组数据，输出一个整数表示有界区域的最大个数。
样例
input
1
4
output
3
Problem solving:
这道题就是一个公式，n条线能组成的有界区域的最大个数是从1加到n。
比赛时候谁知道这是公式啊，画图画到5条线的时候发现的规律写了一遍交了，嘿，还真过了。
佩服用矩快的同学，我是真的不知道咋构建矩阵。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,t;
cin>>t;
while(t--)
{
cin>>n;
ll ans;
ans=(n-1)*(n-2)/2;
cout<<ans<<endl;
}
}蚂蚁和斐波那契
Description:
聪明的小蚂蚁最近学习了斐波那契数列,但是它想到了一个问题：
从L到R之间斐波那契数列和的奇偶是什么呢？
其中Fib[1]=1,Fib[2]=1 .
输入格式
单组输入:
每组输入两个以空格隔开的数字 L 和 R
其中 (0<L<=R<1e18)
输出格式
从 L 到 R 斐波那契数列和的奇偶，如果是奇数输出 "1" (不带引号) ，否则输出 "0" (不带引号)
样例
input
1 2
output
0
Problem solving:
这道题就是个找规律的题没啥好说的，看代码自行体会吧。（我可能写的麻烦了）
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans[55];
int main()
{
ll mid,miid,l,r;
cin>>l>>r;
mid=l%3,miid=r%3;
if(mid==0&&miid==0) puts("0");
else if(mid==miid) puts("1");
else if(mid==0&&miid==1) puts("1");
else if(mid==0&&miid==2) puts("0");
else if(mid==1&&miid==0) puts("0");
else if(mid==2&&miid==0) puts("1");
else if(mid==2&&miid==1) puts("0");
else if(mid==1&&miid==2) puts("0");
return 0;
}蚂蚁装修
Description:
还有一个月就开学了，爱学习的小蚂蚁想庆祝一下！于是它要把它的“家”装修一下。
首先要做的就是贴地板。
小蚂蚁“家”的地面可以看成一个2∗N 的方格 ，它拥有无数块1∗2 和 2∗1的地板。
请你帮下蚂蚁计算一下一共有多少种方法能把地面给放满 。
地板不能切割，也不能重叠。
输入格式
单组输入：
只有一个数字 N
其中 (0<N<1e18)
输出格式
输出放法数对1e9+7取模的结果
样例
input
2
output
2
input
1
output
1
Problem solving:
手动画了几个状态，发现这个个数就是斐波那契数列，但是要求的最大的是1e18项，所以正好可以用矩快解决。注意用long long
Code:
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
struct node{
ll m[2][2];
};
node mul(node a,node b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(ll i=0;i<2;i++)
{
for(ll j=0;j<2;j++)
{
for(ll k=0;k<2;k++)
{
ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
}
}
}
return ans;
}
node poww(node a,ll b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(ll i=0;i<2;i++) ans.m[i][i]=1;
while(b)
{
if(b&1) ans=mul(ans,a);
a=mul(a,a);
b/=2;
}
return ans;
}
node si,jia;
int main()
{
si.m[0][0]=2,si.m[1][0]=1,si.m[0][1]=0,si.m[1][1]=0;
jia.m[0][0]=1,jia.m[1][0]=1,jia.m[0][1]=1,jia.m[1][1]=0;
ll n;
cin>>n;
if(n==1)
{
cout<<1%mod<<endl;return 0;
}
if(n==2)
{
cout<<2%mod<<endl;return 0;
}
node xiaozhu=poww(jia,n-2);
xiaozhu=mul(xiaozhu,si);
cout<<xiaozhu.m[0][0]<<endl;
}蚂蚁的镜像串
Description:
Problem solving:
这道题，，是真的坑啊。
把可以组成镜像串的字母列出来，判断每一个字符，如果出现了不可以组成镜像串的直接就不是镜像串了。如果你也是这样想的这么单纯，恭喜你你会WA很多次。WA到怀疑人生那种。
因为bdpq他们也是可以组成镜像串的。
知道了这一点就可以很简单的解决这个问题了
Code:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
string s;
cin>>t;
while(t--)
{
cin>>s;
int flag=1;
string mid=s;
reverse(mid.begin(),mid.end());
for(int i=0;i<s.size();i++)
{
if((s[i]=='b'&&mid[i]=='d')||(s[i]=='d'&&mid[i]=='b')||(s[i]=='p'&&mid[i]=='q')||(s[i]=='q'&&mid[i]=='p')||(s[i]==mid[i]&&(s[i]=='A'||s[i]=='H'||s[i]=='I'||s[i]=='i'||s[i]=='l'||s[i]=='M'||s[i]=='m'||s[i]=='n'||s[i]=='O'||s[i]=='o'||s[i]=='T'||s[i]=='U'||s[i]=='u'||s[i]=='V'||s[i]=='v'||s[i]=='W'||s[i]=='w'||s[i]=='X'||s[i]=='x'||s[i]=='Y')))
{
continue;
}
else
{
flag=0;
break;
}
}
if(flag==1) puts("YES");
else puts("NO");
}
}蚂蚁赛跑
Description:
小白和小黑非常喜欢养蚂蚁，他们每个人都养了n只蚂蚁。
有一天，他们想比一比谁养蚂蚁的本领更强，于是就举办了一场蚂蚁赛跑比赛。假设蚂蚁都是匀速直线奔跑。
比赛的规则是这样的：每只蚂蚁必须且最多比一场，赢一场得10分，输一场扣10分。平局都不得分也不扣分。
狡猾的小黑同学为了赢得比赛，提前偷到了小白所有蚂蚁得速度，请你帮小黑算一算，他在比赛中最多得多少分。
输入格式
有多组测试案例，最多有100组，对于每一组案例：
第一行以正整数n ,（n≤1000），即每个人的蚂蚁数量。
第二行的n个整数是小黑的蚂蚁的速度。
第三行的n整数是小白的蚂蚁速度。
蚂蚁的速度小于100
输出格式
对于每个输入案例，输出一个整数，这是小黑能够获得的最大分数。
样例
input
2
10 10
10 10
2
10 1
100 8
output
0
0
Problem solving:
贪心，但是我们贪出来，等到我够贪心了再补上
Code:
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! // // _ooOoo_ // o8888888o // 88" . "88 // (| -_- |) // O\ = /O // ____/`---'\____ // .' \| |// `. // / \||| : |||// \ // / _||||| -:- |||||- \ // | | \\ - /// | | // | \_| ''\---/'' | | // \ .-\__ `-` ___/-. / // ___`. .' /--.--\ `. . __ // ."" '< `.___\_<|>_/___.' >'"". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `-. \_ __\ /__ _/ .-` / / // ======`-.____`-.___\_____/___.-`____.-'====== // `=---=' // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //
蚂蚁上树
Description:
蚂蚁上树（Sauteed Vermicelli with minced Pork），又名肉末粉条，是四川省及重庆市的特色传统名菜之一。因肉末贴在粉丝上，形似蚂蚁爬在树枝上而得名。这道菜具体的历史，已不可考。但在四川省、重庆市一带，该菜很常见。
蚂蚁上树通常由粉丝（或者粉条）、肉末为主料，辅以胡萝卜、姜、葱、豆瓣酱等辅料制作而成。成菜后，口味清淡，爽滑美味，色泽红亮，食之别有风味。
蚂蚁想知道这棵树上距离最远的两个点之间的距离
给你一个具有 n 个节点的树
求这棵树上距离最远的两个点之间的距离
输入格式
第一行一个整数 n ，(1≤n≤1e4)
接下来 n−1 行，每行三个整数 x,y,z 表示 x 与 y 之间有一条长度为 z 的边 (1≤x,y≤n,1≤z≤104)
输出格式
一个整数表示树上距离最远的两个点之间的距离
样例
input
5
1 2 9
1 3 3
1 5 2
2 4 10
output
22
Problem solving:
求树的直径，套班子就行啦，别忘了long long
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
ll n,x,y,z,dis[maxn],vis[maxn];
vector<pair<int,int> > v[maxn];
void bfs(ll x)
{
queue<int> q;
q.push(x);
vis[x]=1;
dis[x]=0;
while(!q.empty())
{
x=q.front();
q.pop();
for(int i=0;i<v[x].size();i++)
{
if(!vis[v[x][i].first])
{
q.push(v[x][i].first);
dis[v[x][i].first]=dis[x]+v[x][i].second;
vis[v[x][i].first]=1;
}
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n-1;i++)
{
cin>>x>>y>>z;
v[x].push_back(make_pair(y,z));
v[y].push_back(make_pair(x,z));
}
bfs(1);
ll si=0,jia,ans=0;
for(int i=1;i<=n;i++)
{
if(dis[i]>si)
{
si=dis[i];
jia=i;
}
}
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
bfs(jia);
for(int i=1;i<=n;i++)
{
ans=max(ans,dis[i]);
}
cout<<ans<<endl;
}蚂蚁的游戏
Description:
蚂蚁Bob和蚂蚁Alice是青梅竹蚁，Alice喜欢和Bob一起玩游戏，每当Alice想到新的游戏，都会找Bob一起玩
今天Alice的游戏是这样的：
n堆石子，两人轮流取。每次只能在1堆中取，不能不取，最先取完石子者胜
Alice先取石子，Alice和Bob都非常聪明，拿石子的过程中不会出现失误。
输入格式
第一行有一个整数T，有T组输入数据(T≤50)
每组第一行有一个数n表示有n堆石子，(1≤n≤20000)
第二行有n个非零整数x，表示每堆石子的数量(x≤1e3)
输出格式
请你判断Alice能否在游戏中获胜，如果不能获胜，输出NO。
否则，输出YES，并输出第一次取石子的所有方法（具体参见样例和提示）
样例
input
2
2
45 45
5
5 7 8 9 10
output
NO
YES
3 1
4 0
5 3
提示
对于第一组样例，不论Alice怎么取，Bob总能拿到最后一个石子，所以输出为NO
对于第二组样例，Alice可以第一次取石子有三种取法：
第3堆取出7个，剩下1个
第4堆全部取出，剩下0个
第5堆取出7个，剩下3个
对于每组输出，总是按照堆的编号顺序输出的
Problem solving:
博弈论的问题，好像有板子可以套，但是我并不会。学会了再补吧
Code:
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! // // _ooOoo_ // o8888888o // 88" . "88 // (| -_- |) // O\ = /O // ____/`---'\____ // .' \| |// `. // / \||| : |||// \ // / _||||| -:- |||||- \ // | | \\ - /// | | // | \_| ''\---/'' | | // \ .-\__ `-` ___/-. / // ___`. .' /--.--\ `. . __ // ."" '< `.___\_<|>_/___.' >'"". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `-. \_ __\ /__ _/ .-` / / // ======`-.____`-.___\_____/___.-`____.-'====== // `=---=' // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //
Momenta公司福利 279人发布
