求助两道站外题,玄关(每题一关)
  • 板块学术版
  • 楼主xsmfollower
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/14 18:11
  • 上次更新2024/4/14 21:00:02
查看原帖
求助两道站外题,玄关(每题一关)
1308728
xsmfollower楼主2024/4/14 18:11

20 分 WA:

#include<cstdio>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int N=1510,M=1e4+10;
int n,m,rd[N],rk[N]; bitset<N>f[N]; vector<int>g[N];
struct Edge { int u,v; }e[M],ans[M];
bool cmp(Edge a,Edge b) {
  return (rk[a.v]==rk[b.v]?rk[a.u]>rk[b.u]:rk[a.v]<rk[b.v]);
}
bool cmp2(Edge a,Edge b) { return (a.u==b.u?a.v<b.v:a.u<b.u); }
void toposort() {
  queue<int>q;
  for(int i=1;i<=n;i++) if(!rd[i]) q.push(i);
  while(!q.empty()) {
    int u=q.front(); q.pop();
    for(auto v:g[u])
      if(!(--rd[v])) rk[v]=rk[u]+1,q.push(v);
  }
}
int main() {
  scanf("%d %d",&n,&m);
  for(int i=1;i<=m;i++)
    scanf("%d %d",&e[i].u,&e[i].v),
    g[e[i].u].push_back(e[i].v),g[e[i].v].push_back(e[i].u);
  toposort(),sort(e+1,e+m+1,cmp); int cnt=0;
  for(int i=1;i<=m;i++)
    if(!f[e[i].v][e[i].u])
      ans[++cnt]=e[i],f[e[i].v][e[i].u]=true,f[e[i].v]|=f[e[i].u];
  sort(ans+1,ans+cnt+1,cmp2);
  printf("%d\n",cnt);
  for(int i=1;i<=cnt;i++) printf("%d %d\n",ans[i].u,ans[i].v);
  return 0;
}

15 分 WA:

#include<cstdio>
#include<queue>
using namespace std;
const int N=2e5+10,MOD=1e9+7;
int jdz(int a) { return (a<0?-a:a); }
struct P {
  int num;
  bool operator <(const P &x) const { return jdz(num)>jdz(x.num); }
}a[N];
int main() {
  int n,k,x,cnt=0; priority_queue<P>q; scanf("%d %d %d",&n,&k,&x);
  for(int i=1;i<=n;i++) {
    scanf("%d",&a[i].num);
    if(a[i].num<0) cnt++;
    q.push(a[i]);
  }
  while(k--) {
    int num=q.top().num; q.pop();
      bool flag=(cnt>=0);
    if(cnt&1)
      if(num>=0) num+=x;
      else num-=x;
    else
      if(num>=0) num-=x;
      else num+=x;
    if(num<0&&flag) cnt++;
    q.push((P){num});
  }
  long long ans=1;
  while(!q.empty()) ans=ans*q.top().num%MOD,q.pop();
  printf("%lld",(ans+MOD)%MOD);
  return 0;
}
2024/4/14 18:11
加载中...