10月15日考试总结

第一题

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

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
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<<way[n];
}
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<iostream>
#include<cstdio>
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<<k<<" "<<m<<endl;
  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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
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<<max(u,y);
   return 0;
}