10月15日考试总结

第一题

做题思路
裸的SPFA，搞定！
代码

#include
#include
#include
#include
#include
using namespace std;
int n,m;
int INF=1000004;
int head[100004],biao[100004],way[100003];
struct node
{int f,t,way,nt;
}e[1000003];
int spfa()
{memset(way,INF,sizeof(way));queue<int> q;biao[1]=1;way[1]=0;q.push(1);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].nt){if(way[e[i].t]>way[e[i].f]+e[i].way){way[e[i].t]=way[e[i].f]+e[i].way;if(!biao[e[i].t])biao[e[i].t]=1,q.push(e[i].t);}}biao[u]=0;}cout<int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);e[i].f=a;e[i].t=b;e[i].way=c;e[i].nt=head[a];head[a]=i;}spfa();
}

ps:这次考试我知道了hack快读党的方法,就是少建一行数据，蛤蛤蛤！

第二题

ps:这题原名：USACO[Face The Right Way]
考试思路：
一开始我把它做二分来着,结果搞了好久后发现它根本不符合二分的概念，一气之下打了个暴力，把k从1到n遍历，结果数据太水还给我搞到了70分;
AC思路：
后面看了题解才发现其实枚举k倒是AC思路里面的，但需要加上优化，即用一个z值表示转的次数，我们令F为1，B为0，如果a[i]+z的值为偶数，那么它就需要转向，z++，那么有人要问，它不是一次性只能转k长度吗？z++怎么得k呢?其实我们只要用一个数组j标记即可，如果i要转，那么我们就把j[i+k-1]–；这样的话，z加到那里时，就会自动减掉，那样就不用担心这种问题了，1-n遍历完后，如果z不为0，就说明不可行，否则记录该值;
代码

#include
#include
using namespace std;
int n,ans=0;
char a;
int  b[50003];
int  c[50003];
int pai(int u)
{int biao[50003]={0};ans=0; int zhi=0;for(int i=1;i<=n;i++) {if((c[i]+zhi)%2==1){ans++;zhi++;biao[i+u-1]=-1;} zhi+=biao[i];}if(zhi)return 0;return 1;
}
int main()
{ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>a;if(a=='B')c[i]=1;else c[i]=0;}int m,k;for(int mid=1;mid<=n;mid++)if(pai(mid)){m=ans;k=mid;}cout<" "<return 0;
}

第三题

做题思路
这个如果没有k，其实很简单，就把A能力从大到小排序，然后取B值的最长上升子序列(不需要lower_bound这些东西，只要在排序里面改一下就行)，然而k值在考试的时候没有处理好;
AC思路
主要是对于K的处理，其实我们只要对i和i-1进行处理就行(2<=i<=n),因为A递减，B递增，所以如果i与i-1大于K那么后面也必定与i-1不满足,所以只要不满足就断开开新队，然后记录最长的一队的长度就可以了;
代码

#include
#include
#include
#include
#include
using namespace std;
int n,k;
struct node
{int a,b;
}e[150000],q[150000];
int v(const node &a,const node &b)
{if(a.a==b.a)return a.b>b.b;return a.a>b.a;
}
int c(int x)
{if(x>0)return x;return -x;
}
int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){cin>>e[i].a>>e[i].b;}sort(e+1,e+n+1,v);int num=1;q[1].b=e[1].b;q[1].a=e[1].a;int u=0;for(int i=2;i<=n;i++){if(e[i].b>q[num].b)num++,q[num].a=e[i].a,q[num].b=e[i].b;}    int y=1;int a1=q[1].a,b1=q[1].b;for(int i=2;i<=num;i++){if(c(q[i].a-a1)+c(q[i].b-b1)>k)u=max(u,y),y=1;else y++;a1=q[i].a,b1=q[i].b;}cout<y);return 0;
}

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