光说不练是假把式，先给各大巨巨们一个刷题链接：戳我进入刷题OJ
这届比赛水题有点多，想拿奖保证好手速即可。但是想拿高名次并不太容易
A。常规做法我不太会，但是根据题目的数据发现，可以开个这么大的数组哈哈，那么万能的暴力保证1A。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500;
int num[maxn];
int main(){
//freopen("input.txt","r",stdin);
int n;
int a,b,c;
while(scanf("%d",&n)!=EOF){
memset(num,0,sizeof(num));
while(n--){
scanf("%d%d%d",&a,&b,&c);
for(int i=b;i<b+c;i++)
num[i]+=a;
}
int ans=0;
for(int i=1;i<=180;i++)
ans=max(ans,num[i]);
printf("%d\n",ans);
}
return 0;
}
B。简单题，比A更好做。O（sqrt（n））判断质数即可。关键是注意同等距离的时候取比n大的那个素数
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int is_prime(int n){
for(int i=2;i*i<=n;i++)
if (n%i==0) return 0;
return 1;
}
int main(){
//freopen("input.txt","r",stdin);
int i,k;
scanf("%d",&n);
while(n--){
scanf("%d",&k);
for(i=0;;i++){
if (is_prime(k+i)){
printf("%d\n",k+i);
break;
}
else if (is_prime(k-i)){
printf("%d\n",k-i);
break;
}
}
}
return 0;
}
C。这个题一开始把我吓住了，比赛时候用bin神模板的强联通缩点化图为树得到多少个叶子节点，然后ans=（叶子节点数+1）/2。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010;
const int maxm=20010;
struct Edge{
int to,next;
bool cut;
}edge[maxm];
int head[maxn],tot;
int low[maxn],dfn[maxn],stack[maxn],belong[maxn];
int Index,top;
int block;
bool instack[maxn];
int bridge;
void addedge(int u,int v){
edge[tot].to=v;
edge[tot].next=head[u];
edge[tot].cut=false;
head[u]=tot++;
}
void Tarjan(int u,int pre){
int v;
low[u]=dfn[u]=++Index;
stack[top++]=u;
instack[u]=true;
for(int i=head[u];i!=-1;i=edge[i].next){
v=edge[i].to;
if (v==pre) continue;
if (!dfn[v]){
Tarjan(v,u);
if (low[u]>low[v]) low[u]=low[v];
if (low[v]>dfn[u]){
bridge++;
edge[i].cut=true;
edge[i^1].cut=true;
}
}
else if (instack[v]&&low[u]>dfn[v]) low[u]=dfn[v];
}
if (low[u]==dfn[u]){
block++;
do{
v=stack[--top];
instack[v]=false;
belong[v]=block;
}
while(v!=u);
}
}
void init(){
tot=0;
memset(head,-1,sizeof(head));
}
int du[maxn];
void solve(int n){
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(stack,0,sizeof(stack));
memset(belong,0,sizeof(belong));
memset(instack,false,sizeof(instack));
Index=top=block=0;
Tarjan(1,0);
int ans=0;
memset(du,0,sizeof(du));
for(int i=1;i<=n;i++)
for(int j=head[i];j!=-1;j=edge[j].next)
if (edge[j].cut)
du[belong[i]]++;
for(int i=1;i<=block;i++)
if (du[i]==1) ans++;
printf("%d\n",(ans+1)/2);
}
int main(){
//freopen("input.txt","r",stdin);
int n,u,v,i;
while(scanf("%d",&n)!=EOF){
init();
for(i=1;i<n;i++){
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
solve(n);
}
return 0;
}
D。图论题
先说说自己的错误想法。由于题中说明的是只能买卖一次求最大，那么我能够到的点取最小和最大作差就是最终答案。
因此跑树形DP，从起点1跑一次，1到其他点的最大最小，从终点n跑一次，n到其他点的最大最小。当时代码写得没有问题，贴出来如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100050;
const int maxm=500050;
struct node{
int u,v;
int next;
}edge[maxm];
int num[maxn];
int dp[maxn];
int head[maxn];
int tot,ans;
bool vis[maxn];
void addedge(int u,int v){
edge[tot].u=u;
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
}
void GetMin(int u){
vis[u]=true;
int tempmax;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v,flag=0;
if (vis[v]) continue;
GetMin(v);
dp[u]=max(dp[u],dp[v]);
}
dp[u]=max(dp[u],num[u]);
}
void GetMax(int u){
vis[u]=true;
int tempmin;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v,flag=0;
if (vis[v]) continue;
GetMin(v);
dp[u]=min(dp[u],dp[v]);
}
dp[u]=min(dp[u],num[u]);
}
int main(){
freopen("input.txt","r",stdin);
int n,m,i;
int a,b,c;
while(scanf("%d%d",&n,&m)!=EOF){
memset(head,-1,sizeof(head));
memset(num,0,sizeof(num));
ans=tot=0;
for(i=1;i<=n;i++) scanf("%d",&num[i]);
for(i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
if (c==1){
addedge(a,b);
}
else{
addedge(a,b);
addedge(b,a);
}
}
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
GetMax(n);
for(i=1;i<=n;i++) printf("%d%c",dp[i],i==n?'\n':' ');
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++) dp[i]=1000000;
GetMax(1);
for(i=1;i<=n;i++) printf("%d%c",dp[i],i==n?'\n':' ');
printf("%d\n",ans);
}
return 0;
}
错误原因：处理不了图中的回路问题
其实我的思路已经跟题解比较接近了，一是贪心找最大最小，但是是从起点能到的点找最小，从能到终点的点找最大。二是必须能够处理回路和权值，Spfa和Bellman-fold都是好选择。
Spfa算法：
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100010;
const int maxm=500010;
int a[maxn],b[maxn],head1[maxn],head2[maxn],tot;
struct node{
int u,v;
int next;
}edge[maxm];
void addedge(int u,int v){
edge[tot].u=u;
edge[tot].v=v;
edge[tot].next=head1[u];
head1[u]=tot++;
edge[tot].u=v;
edge[tot].v=u;
edge[tot].next=head2[v];
head2[v]=tot++;
}
int spfa(int s,int n){
queue<int> q;
int x,i,v;
int mark1[maxn],mark2[maxn];
memset(mark1,0,sizeof(mark1));
memset(mark2,0,sizeof(mark2));
mark1[s]=1;
mark2[n]=1;
q.push(s);
while(!q.empty()){
x=q.front();
q.pop();
for(i=head1[x];i!=-1;i=edge[i].next){
v=edge[i].v;
a[v]=min(a[v],a[x]);
if (!mark1[v]){
mark1[v]=1;
q.push(v);
}
}
}
q.push(n);
while(!q.empty()){
x=q.front();
q.pop();
for(i=head2[x];i!=-1;i=edge[i].next){
v=edge[i].v;
b[v]=max(b[v],b[x]);
if (!mark2[v]){
mark2[v]=1;
q.push(v);
}
}
}
int ans=0;
for(i=1;i<=n;i++)
if (mark1[i]&&mark2[i])
ans=max(ans,b[i]-a[i]);
return ans;
}
int main(){
int n,m,v,u,x,i;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
tot=0;
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
while(m--){
scanf("%d%d%d",&u,&v,&x);
addedge(u,v);
if (x==2) addedge(v,u);
}
printf("%d\n",spfa(1,n));
}
return 0;
}
另外，在网上还可以搜到一种强连通缩点之后继续构造新图进行dfs搜索的，本人觉得那种方法必须利用模板，没有Spfa好写，没有在此贴出
E。最经典的二维DP题。初始化第一行第一列，然后dp[i][j]只与dp[i-1][j]，dp[i][j-1]有关。dp[i][j]为走到(i,j)方格时的最大值
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=50;
int n,m;
int num[maxn][maxn];
int dp[maxn][maxn];
int main(){
//freopen("input.txt","r",stdin);
int i,j;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&num[i][j]);
memset(dp,0,sizeof(dp));
dp[1][1]=num[1][1];
for(i=2;i<=m;i++) dp[1][i]=dp[1][i-1]+num[1][i];
for(i=2;i<=n;i++) dp[i][1]=dp[i-1][1]+num[i][1];
//for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// printf("%d%c",dp[i][j],j==m?'\n':' ');
for(i=2;i<=n;i++)
for(j=2;j<=m;j++)
if (dp[i-1][j]>dp[i][j-1])
dp[i][j]=dp[i-1][j]+num[i][j];
else dp[i][j]=dp[i][j-1]+num[i][j];
printf("%d\n",dp[n][m]);
}
return 0;
}
F。读题觉得有点费劲。其实翻译过来很好懂，就是个定义了个物品竞拍的原则，相当于个水模拟：
1.是否有单独出现的竞拍价格。若有，选择其中最小的
2.若1不成立，则取最小的其中的竞拍价格，且找到第一个出此竞拍价格的人作为竞拍者
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2000;
int check[maxn];
char str[maxn][10];
int num[maxn];
int n,m;
int getvalid(){
int i,j;
for(i=1;i<=n;i++)
if (check[i]==1){
for(j=1;j<=m;j++)
if (num[j]==i){
printf("The winner is %s\n",str[j]);
printf("The price is %d\n",num[j]);
}
break;
}
if (i==n+1) return -1;
return 1;
}
int main(){
//freopen("input.txt","r",stdin);
int i;
while(scanf("%d%d",&n,&m)!=EOF){
memset(check,0,sizeof(check));
for(i=1;i<=m;i++){
scanf("%s%d",str[i],&num[i]);
check[num[i]]++;
}
int ans=getvalid();
if (ans!=-1){
continue;
}
for(i=1;i<=n;i++)
if (check[i]){
for(int j=1;j<=m;j++)
if (num[j]==i){
printf("The winner is %s\n",str[j]);
printf("The price is %d\n",num[j]);
}
break;
}
}
return 0;
}
G。题目废话太多。。其实是个水贪心题
题目定义了两个价格容易把人弄晕。其实把根据距离算出的费用与买种子的费用算成一个总体费用当作在该种子站购买种子的费用，然后就发现，可以排序一发从小到大贪心购买即得到最小
#include"iostream"
#include"stdio.h"
#include"stdlib.h"
#include"algorithm"
using namespace std;
struct station
{
int price;
int count;
}st[10000];
int cmp(station x,station y)
{
if(x.price<y.price)
return 1;
else return 0;
}
int main()
{
// freopen("input.txt","r",stdin);
int t1,t2,t3;
int k,e,n;
int i;
while(cin>>k>>e>>n)
{
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
st[i].price=t3+e-t1;
st[i].count=t2;
}
sort(st+1,st+n+1,cmp);
// for(i=1;i<=n;i++)
// cout<<st[i].price<<" "<<st[i].count<<endl;
int temp=k;
int ans=0;
for(i=1;i<=n;i++)
{
if(temp>st[i].count)
{
ans+=st[i].price*st[i].count;
temp-=st[i].count;
}
else
{
ans+=temp*st[i].price;
break;
}
}
cout<<ans<<endl;
}
return 0;
}
H。看到区间分配问题，立马想到线段树。。但是这个，我不太会。
从网上找到了个很好的题解分享给大家：
题解写到这，总结下：
这次比赛感觉是场手速赛，出ABCEFG都不难关键是一开始找到这些题并把握好姿势AC，尽可能1A过，DH这种题并不太难，但是在比赛场上要想到这种方法对于我这种弱弱还是比较难。继续加油
京公网安备 11010502036488号