TEST 3

A. 不要落后

• 按照规则找就好了

  map<string, int> q;
  set<int> g;
  
  signed main() {
      IOS;
      int n;
      cin >> n;
      for (int i = 1; i <= n; i++) {
          string s;
          int x;
          cin >> s >> x;
          q[s] += x;
      }
      for (auto x : q) {
          int y = x.second;
          g.insert(y);
      }
      if (g.size() == 1) {
          if (q.size() == 1) {
              for (auto x : q) {
                  cout << x.first;
                  return 0;
              }
          } else {
              cout << "Tie";
          }
      }
          g.erase(g.begin());
          for (auto x : q) {
              int y = x.second;
              if (y == *g.begin()) {
                  cout << x.first;
                  return 0;
              }
          }
  
          return 0;
  }

B. 矩形挡拆

• 依然是个枚举的题

  int x[5],y[5];
  bool a[5];
  signed main()
  {
      for(int i=1;i<=4;i++)
      {
          cin>>x[i]>>y[i];
      }
      if(x[3]<=x[1] && x[4]>=x[1])
      {
          if(y[3]<=y[1] && y[4]>=y[1])
          {
              a[1]=1;
          }
          if(y[3]<=y[2] && y[4]>=y[2])
          {
              a[2]=1;
          }
      }
      if(x[3]<=x[2] && x[4]>=x[2])
      {
          if(y[3]<=y[1] && y[4]>=y[1])
          {
              a[4]=1;
          }
          if(y[3]<=y[2] && y[4]>=y[2])
          {
              a[3]=1;
          }
      }
      if(a[1] && a[2])
      {
          if(a[3] && a[4])
          {
              cout<<0;
              return 0;
          }
          cout<<abs(x[2]-x[4])*abs(y[2]-y[1]);
          return 0;
      }
      if(a[3] && a[2])
      {
          cout<<abs(x[2]-x[1])*abs(y[3]-y[1]);
          return 0;
      }
      if(a[3] && a[4])
      {
          cout<<abs(x[3]-x[1])*abs(y[2]-y[1]);
          return 0;
      }
      if(a[1] && a[4])
      {
          cout<<abs(x[2]-x[1])*abs(y[4]-y[2]);
          return 0;
      }
      cout<<abs(x[2]-x[1])*abs(y[2]-y[1]);
      return 0;
  }

C. 井井游戏

• 依然是个模拟

  bool win[27][27],f[8][27];
  vector<int> a[8];
  string s[3];
  int dry,tdy;
  int main()
  {
      cin>>s[0]>>s[1]>>s[2];
      for(int i=0;i<3;i++)
      {
          for(int j=0;j<3;j++)
          {
              if(!f[i][s[i][j]-'A'])
              {
                  f[i][s[i][j]-'A']=1;
                  a[i].push_back(s[i][j]-'A');
              }
              if(!f[i+3][s[j][i]-'A'])
              {
                  f[i+3][s[j][i]-'A']=1;
                  a[i+3].push_back(s[j][i]-'A');
              }
          }
          if(!f[6][s[i][i]-'A'])
          {
              f[6][s[i][i]-'A']=1;
              a[6].push_back(s[i][i]-'A');
          }
          if(!f[7][s[i][2-i]-'A'])
          {
              f[7][s[i][2-i]-'A']=1;
              a[7].push_back(s[i][2-i]-'A');
          }
          
      }
      for(int i=0;i<8;i++)
      {
          if(a[i].size()==1)
          {
              if(win[a[i][0]][a[i][0]])continue;
              win[a[i][0]][a[i][0]]=1;
              dry++;
          }
      }
      for(int i=0;i<8;i++)
      {
          if(a[i].size()==2)
          {
              if(win[a[i][0]][a[i][1]])continue;
              win[a[i][0]][a[i][1]]=1;
              win[a[i][1]][a[i][0]]=1;
              tdy++;
          }
      }
      cout<<dry<<'\n'<<tdy;
      return 0;
  }

D. 区间切

• 从后往前去算max就好了

  using namespace std;
  #define MAX 10005
  int a[MAX], f[MAX];
  
  signed main() {
      IOS;
      int n, k;
      cin >> n >> k;
      for (int i = 1; i <= n; i++) {
          cin >> a[i];
      }
      for (int i = 1; i <= n; i++) {
          int g = 0;
          for (int j = i; j >= max(i + 1 - k, 1); j--) {
              g = max(g, a[j]);
              f[i] = max(f[i], f[j - 1] + g * (i - j + 1));
          }
      }
      cout << f[n] << endl;
  
      return 0;
  }

E. Wonderhoy 子集

• 预处理+刷表就好了

  const int N = 1024, mod = 1e9 + 7;
  int n, s[N], DP[N], ans;
  
  void dfs(int x, int sum)
  {
      if (x <= n)
      {
          s[sum]++;
      }
      else
      {
          return;
      }
      for (int i = 0; i <= 9; i++)
      {
          if (!(sum & (1 << i)))
          {
              dfs(x * 10 + i, sum | (1 << i));
          }
      }
  }
  
  signed main()
  {
      IOS;
      cin >> n;
      for (int i = 1; i <= 9; i++)
      {
          dfs(i, 1 << i);
      }
      DP[0] = 1;
      for (int i = 0; i < N; i++)
      {
          for (int j = N - 1; j >= 0; j--)
          {
              if (!(i & j))
              {
                  DP[i | j] = (DP[i | j] + (DP[j] * s[i])) % mod;
              }
          }
      }
      for (int i = 1; i < N; i++)
      {
          ans = (ans + DP[i]) % mod;
      }
      cout << ans << endl;
  
      return 0;
  }

F. 子树（题意修改）

很好的一个树上DP,把集合的思路想的很明确

#include<bits/stdc++.h>
#define M 100005
#define P 1000000007
#define LL long long
using namespace std;
int hd[M],nxt[M+M],to[M+M],cnte;
LL dp[M],cnt[M],ans;
/*  一个树上的连通块，最浅的点是唯一的
dp:所有以i为最浅的点的连通块的贡献
cnt:以i为最浅的点的连通块的个数
*/
void addedge(int a,int b){
	nxt[++cnte]=hd[a];
	to[cnte]=b;
	hd[a]=cnte;
}
void dfs(int x,int f){
	dp[x]=cnt[x]=1;//只放i这一个点
	for(int i=hd[x];i;i=nxt[i]){
		int y=to[i];
		if(y==f)continue;
		dfs(y,x);
		//考虑把y这颗子树对x的贡献加进来
		//为了联通所以要么取含y的一个连通块，要么一个点都不取。 
		//所以y这个子树对于x来说有cnt[y]+1种方案
		dp[x]=((cnt[y]+1)*dp[x]%P+cnt[x]*dp[y]%P)%P;
		//     |设此处为part1    |此处为part2 
		//part1:因为y的取法对之前的点的取法没有影响,
		//		y只是让方案数变成原本的(cnt[y]+1),所以之前点的贡献变成(cnt[y]+1) 倍。
		//part2:同part1,所以y的贡献变成cnt[x]倍. 
		cnt[x]=cnt[x]*(cnt[y]+1)%P;
	}
	ans=(ans+dp[x])%P;//枚举连通块中最浅的点，累加答案 
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1,a,b;i<n;i++){
		scanf("%d%d",&a,&b);
		addedge(a,b);
		addedge(b,a);
	}
	dfs(0,-1);
	printf("%lld\n",ans);
	return 0;
}