百度9月26日笔试题

#include <algorithm>
#include <set>
#include <stdio.h>
#include <string.h>
#include <stack>

typedef long long LL;
#define N 100010

using namespace std;

int to[N], we[N];

int is_true[N], vis[N];
int dfs(int u) {
 vis[u] = 1;
 {
  int v = to[u], w = we[u];
  if (w == 2) {
   if (v == u)
    is_true[u] = 0;
   else
    is_true[u] = 1;
  }
  else {
   if (vis[v]) {
    is_true[u] = 1;
   }
   else {
    if (is_true[v] == -1)
     dfs(v);
    is_true[u] = is_true[v];
   }
  }
 }
 vis[u] = 0;
 return is_true[u];
}

int main() {

 int n;
 scanf("%d", &n);
 for (int u = 1; u <= n; u++) {
  int t, v;
  scanf("%d %d", &t, &v);
  to[u] = v;
  we[u] = t;
 }
 int ans = 0;
 for (int i = 1; i <= n; i++) {
  if (dfs(i)) {
   ans++;
  }
 }
 printf("0 %d\n", n - ans);
 return 0;
}

第二题：

	#include <algorithm>
#include <set>
#include <stdio.h>
#include <string.h>



	typedef long long LL;
#define N 100010



	using namespace std;



	int val[N], lft[N], rgt[N], a[N], b[N];
int m;



	inline int lowbit(int x) {
  return x & (-x);
}



	void add(int p) {
  while (p <= m) {
    val[p]++;
    p += lowbit(p);
  }
}



	int sum(int p) {
  int res = 0;
  while (p) {
    res += val[p];
    p -= lowbit(p);
  }
  return res;
}



	int main() {

  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  sort(b+1, b+n+1);
  m = unique(b+1, b+n+1) - b - 1;
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(b+1, b+m+1, a[i]) - b;
  }



	  LL tot = 0;
  for (int i = 1; i <= n; i++) {
    lft[i] = sum(a[i]-1);
    add(a[i]);
  }



	  pair<int, int> ans(1<<30, 1<<30);
  memset(val, 0, sizeof(val));
  for (int i = n; i; i--) {
    rgt[i] = sum(a[i]-1);
    add(a[i]);
    tot += rgt[i];
    ans = min(ans, make_pair(lft[i] - rgt[i], i));
  }



	  printf("%lld %d", tot+ans.first, ans.second);



	  return 0;
}