T1.简单树(easy.cpp)

题目描述

给定一棵 n 个点的树,你需要给每条边赋值 01,求树上所有点对之间的简单路径权值总和的最大值,并输出方案。

一条路径的权值定义为这条路径上所有边权的异或和。

题解

引理

可以知道, ans(x,y) = ans(x, root) \oplus ans(y, root)。将树想象成一颗有根树,不管上面的路径是什么,当前节点跟父亲之间的路决定了 ans(root, now) ,我们设 a_ians(root, i),显然这个 a 数组是可以自己决定的。

答案最大化

怎么让答案最大呢?设答案为\texttt 1的点有 x 个,答案为\texttt 0的点有 y 个,有x + y = n,则根据基本不等式,xy 的最大值在 x=y时。

根据点的数量和边的关系进行赋值即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 1e6 + 10;
int n;
struct edge{int u, v;}G[N];
int a[N];
int main()
{
  // freopen(".in", "r", stdin);
  // freopen(".out", "w", stdout);
  int u, v;
  scanf("%d", &n);
  for(int i = 1; i <= n - 1; i++) {
    scanf("%d%d", &u, &v);
    G[i].u = u, G[i].v = v;
  }
  printf("%d\n", (n / 2) * (n - n / 2));
  for(int i = 1; i <= n / 2; i++) a[i] = 0;
  for(int i = n / 2 + 1; i <= n; i++) a[i] = 1;
  for(int i = 1; i <= n - 1; i++) {
    printf("%d ", a[G[i].u] != a[G[i].v]);
  }
  return 0;
}

T2.扑克(poker.cpp)

题目描述

你在玩德州扑克,现在手上有两张牌,桌上有三张牌,你要知道你是否必胜。

原题:
一副去掉大小王的扑克牌包含 13 种不同的数值:2,3,4,5,6,7,8,9,T,J,Q,K,A,它们的大小从左到右依次递增。扑克牌中有四种不同的花色,用 S,H,D,C 表示,每一种花色都有 13 张牌,分别对应每一种数值。在德州扑克中,我们只需要考虑这 52 张牌。

一副手牌包含 5 张扑克牌,他们可能会形成若干种牌型,按照从大到小的顺序依次为:

  • 同花顺:花色相同的顺子(顺子的定义见下方),例如同花色的 T,J,Q,K,A。
  • 四条:存在四张大小相同的牌,例如任意花色的 T,T,T,T,2。
  • 葫芦:有三张牌大小相同,另外两张牌大小相同,例如任意花色的 T,T,T,J,J。
  • 同花:五张牌花色相同,例如同花色的 7,J,Q,K,A。
  • 顺子:五张牌大小连续,例如任意花色的 2,3,4,5,6, T,J,Q,K,A。特殊地,A,2,3,4,5 也是一个顺子(但是 K,A,2,3,4 不是)。因此一共有 10 种不同数值的顺子,它们的第一张牌分别是 A,2,3,4,5,6,7,8,9,T。
  • 三条:存在三张大小相同的牌,例如任意花色的 T,T,T,J,Q。
  • 两对:存在两个大小不同的对子(一个对子是两张大小一样的牌),例如任意花色的 T,T,Q,Q,K。
  • 对子:存在两张大小相同的牌,例如任意花色的 T,T,J,Q,K。
  • 高牌:不满足以上任何一个牌型的手牌都是高牌。

一副手牌可能同时满足很多个不同的牌型,这个时候我们会把最大的那个牌型作为这副手牌的牌型。

我们可以通过如下方式来比较两副手牌的大小:

  • 如果两副手牌牌型不同,那么牌型较大的手牌更大。
  • 如果两副手牌都是顺子或者都是同花顺,那么按照顺子第一张牌的大小排序,从小到大分别为 A,2,3,4,5,6,7,8,9,T,即 A,2,3,4,5 是最小的顺子,T,J,Q,K,A 是最大的顺子。
  • 否则,我们按照(出现次数,数值)的双关键字从大到小把这五张牌排序,例如 K,K,T,T,T 排序后就是 T,T,T,K,K;2,T,T,K,A 排序后是 T,T,A,K,2。
  • 比较两副牌的字典序。
  • 注意,牌的花色只影响第一步比较牌型,并不影响后面两步的比大小。

手牌更大的玩家将获得胜利,如果两方的手牌一样大,则视为平局。

Haitang 在和 dXqwq 玩德州扑克。她们会先给每人发两张牌,再在桌面发三张牌,再进行一轮加注,再在桌面发两张牌,最后每个人在桌面的五张牌和自己的两张牌中组出最大的牌型,赢家拿走所有筹码。

dXqwq 是大聪明,所以她会用一个聪明的策略:如果在翻开桌面的三张牌之后,无论接下来翻开的牌和 Haitang 手里的牌是什么,她都能赢得胜利,她就会全押(all in),否则她就会过牌(check)或者弃牌(fold)。

虽然 dXqwq 很会博弈,但是她不会判定自己是否必胜。你需要帮助 dXqwq 完成这件事情。如果完成了,dXqwq 会将自己赢得的筹码分你一半。

不出意料地,dXqwq 过了一个小时便垂头丧气地来找你了:她把零花钱输光了。

对于每组数据,如果 dXqwq 必胜,输出 allin,否则输出 check

题解

我们手中有两张固定的牌,对手手中还有其他牌。对于除了同花顺的牌型,对于牌型的花色要求都不是很高,所以对手可以拿出炸弹。考虑最大的炸弹AAAA,虽然我将 A 都拿光了,但对手依旧可以根据公共牌组出同花顺。所以只考虑同花顺的情况。

如果是同花顺,什么情况对手可以掏出更大的同花顺呢?

  • Case1:公共牌有任意一张大于两张手牌,且对手可以用公共牌组同花顺,且手牌小于10
  • Case2:公共牌有一张A,且这张A被我组同花顺

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
int T;
/*
只有同花才可以
前两个比后面的大,对手就无法构造
如果我是12345,必输
54321,必输
15234,必胜
*/
int dic[200];
int main()
{
  freopen("poker.in", "r", stdin);
  freopen("poker.out", "w", stdout);
  scanf("%d", &T);
  for(int i = 2; i <= 9; i++) {
    dic[i + '0'] = i;
  }
  dic['A'] = 14;
  dic['T'] = 10, dic['J'] = 11, dic['Q'] = 12, dic['K'] = 13;
  char s1[5], s2[5], s3[5], s4[5], s5[5];
  while(T--) {
    scanf("%s%s%s%s%s", s1, s2, s3, s4, s5);
    int t1 = dic[s1[1]], t2 = dic[s2[1]], r0 = dic[s3[1]], r1 = dic[s4[1]], r2 = dic[s5[1]];
    int h1 = s1[0], h2 = s2[0], h3 = s3[0], h4 = s4[0], h5 = s5[0];
    int flag = false;
    if(h1 == h2 && h2 == h3 && h3 == h4 && h4 == h5) {
      flag = true;
      priority_queue<int> q;
      q.push(t1); q.push(t2); q.push(r0); q.push(r1); q.push(r2);
      int tp = q.top(); q.pop();
      flag = true;
      int maxx = tp;
      while(!q.empty()) {
        int tmp = q.top(); q.pop();
        // printf("%d %d\n", tp, tmp);
        if(abs_sub(tmp, tp) != 1) flag = false;//不连续
        tp = tmp;
      }
      if(t1 < 10 && t2 < 10 && (t1 < r0 || t1 < r1 || t1 < r2) and (t2 < r0 || t2 < r2 || t2 < r1)) flag = false;
        //有A,除了自己是最大
      // else if(r0 == 14 || r1 == 14 || r2 == 14) flag = false;
    }
    if((t1 == 14 && t2 == 5) || (t1 == 5 && t2 == 14)) {
      t1 = t1 == 14 ? 1 : 5, t2 = t2 == 14 ? 1 : 5;
      priority_queue<int> q;
      q.push(t1); q.push(t2); q.push(r0); q.push(r1); q.push(r2);
      int tp = q.top(); q.pop();
      flag = true;
      while(!q.empty()) {
        int tmp = q.top(); q.pop();
        // printf("%d %d\n", tp, tmp);
        if(abs_sub(tmp, tp) != 1) flag = false;//不连续
        tp = tmp;
      }
    }
    if(flag) printf("allin\n");
    else printf("check\n");
  }
  return 0;
}

T7.故乡的老树(extree.cpp)

相同题目:CF686D/CF685B – Kay and Snowflake

题目描述

给出一颗以\texttt 1为根的树,求所有子树的重心编号,如果有多个,则按照节点编号从小到大输出。

题解

树的重心

在本题中,题目给出的信息是:到这颗子树所有点的距离之和最小的点,这个就是树的重心,但是如果不知道重心的其它性质,这个题目就不是绿题了……考虑到我现在还不会树剖,做这道题之前我还是不知道重心是什么的。

重心的性质:
  • 以树的重心为根时,所有子树不超过整棵树大小的一半
  • 树中所有点到重心的距离之和是最短的
  • 一颗树中至多有两个重心,并且这两个重心一定是相连的
  • 把两棵树通过一条边相连得到一颗新的树,那么新的树的重心在连接原来两个重心的路径上,且链为重链
  • 在一颗树上添加一个点或者删除一个点,重心的位置最多移动一格
  • 当某节点的重儿子的体积的两倍小于该节点的体积,该点为该颗树的重心

做法

有了上面你的性质,我们先递归到底层,叶子节点的重心就是自己,标记完之后,回溯。回溯了我们往上找父亲,直到找到一个重心。

关于是否是重心,判断可以用最后一条性质。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 1e6 + 10;
int n, q;
struct edge{
  int to, nxt;
}G[N << 1];
int head[N];
int cnt;
inline void init() {
  for(int i = 1; i <= n; i++) {
    head[i] = -1;
  }
}
inline void add_edge(int u, int v) {
  G[++cnt] = (edge){v, head[u]};
  head[u] = cnt;
}
int siz[N], maxs[N], pre[N], ans[N][2];
inline void get_v(int pos, int fa) {
  siz[pos] = 1, pre[pos] = fa;
  for(int i = head[pos]; i != -1; i = G[i].nxt) {
    if(G[i].to == fa) continue;
    get_v(G[i].to, pos);
    siz[pos] += siz[G[i].to];
    if(siz[G[i].to] > siz[maxs[pos]]) maxs[pos] = G[i].to;
  }
  // printf("%d\n", pos);
}
inline bool check(int pos, int fa) {
  return max(siz[maxs[pos]], siz[fa] - siz[pos]) * 2 <= siz[fa];
}
inline void dfs(int pos, int fa) { 
  if(!maxs[pos]) {ans[pos][0] = pos; return;}
  for(int i = head[pos]; i != -1; i = G[i].nxt) {
    if(G[i].to == fa) continue;
    dfs(G[i].to, pos);
  }
  int preans = ans[maxs[pos]][0];
  while(!check(preans, pos)) preans = pre[preans];
  ans[pos][0] = preans;
  if(preans != pos && check(pre[preans], pos)) {
    ans[pos][1] = pre[preans];
    if(ans[pos][0] > ans[pos][1]) swap(ans[pos][0], ans[pos][1]);
  }
}
int main()
{
  // freopen("extree2.in", "r", stdin);
  // freopen(".out", "w", stdout);
  scanf("%d%d", &n, &q);
  init();
  int u, v;
  for(int i = 2; i <= n; i++) {
    scanf("%d", &u);
    add_edge(u, i);
    add_edge(i, u);
  }
  get_v(1, 0);
  dfs(1, 0);
  // for(int i = 1; i <= n; i++) {
  //   printf("%d: %d %d\n", i, maxs[i], siz[i]);
  // }
  int d;
  for(int i = 1; i <= q; i++) {
    scanf("%d", &d);
    printf("%d ", ans[d][0]);
  }
  return 0;
}