Java教程

11, 7 题解报告

本文主要是介绍11, 7 题解报告，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

T1 签到题

模拟就好。

code

#include<bits/stdc++.h>
using namespace std;

int read() {
 int x = 0, f = 1; char c = getchar();
 while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
 while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
 return x * f;
}
int n, now = 1, Ans;
priority_queue<int, vector<int>, greater<int> >q;
int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
  	int x = read();
  	if(x == now) {
	  now = x + 1;
	  while(!q.empty() && (int)q.top() == now) {
	  	 now++;
	  	 q.pop();
	  }	 
	  continue;
	}
  	else {
  	  while(!q.empty() && (int)q.top() == now) {
	  	 now++;
	  	 q.pop();
	  }
	  if(now == x) 	Ans = max(Ans, (int)q.size());
  	  else {
  	    q.push(x);
  	    Ans = max(Ans, (int)q.size());
	  }
	}
  }
  cout<<Ans;
  return 0;
}

T2 Z^2∼N

打表找规律，然后大力分类讨论

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 5;
int read() {
 int x = 0, f = 1; char c = getchar();
 while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
 while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
 return x * f;
}
int n, m, a[MAXN];
struct node{int x, y;}b[MAXN];
signed main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) {
  	int x = read(), y = read();
  	if(x == 0 && y == 0) a[i] = 0;
  	int ret = abs(x) + abs(y);
  	int cs = 1 + 2 * ret * (ret - 1);
    if (x > 0 && y == 0) a[i] = cs;
  	if(x == 0 && y > 0) a[i] = cs + 2 * (ret - 1) + 1;
  	int fx = cs + 2 * (ret - 1) + 1;
	if(x == 0 && y < 0) a[i] = cs + ret * 2 + (ret - 1) * 2 + 1;	 
	if(x > 0 && y > 0) a[i] = cs + (y - 1) * 2 + 1;
	if(x > 0 && y < 0) a[i] = cs + abs(y) * 2;
    if(x < 0 && y >= 0) a[i] = fx + abs(x);
    fx = fx + ret;
    if(x < 0 && y < 0) a[i] = fx + abs(y); 
  }
  for (int i = 1; i <= m; i++) {
  	int val = read();
  	if(val == 0) {b[i].x = 0, b[i].y = 0; continue;}
  	int y = sqrt((val - 1) / 2), ret;
  	ret = y;
  	for (int j = max(y - 1, 0ll); j <= y + 30; j++) {
  	  if (1 + 2 * j * (j - 1) <= val && 1 + 2 * j * (j + 1) > val) {ret = j; break;}	
	} 
	int cs = 1 + 2 * ret * (ret - 1);
    if(val == cs) b[i].x = ret, b[i].y = 0;
    if(val >= cs + 1 && val <= cs + 2 * (ret - 1)) {
	  int cz = val - cs;
	  if(cz & 1) {
	  	b[i].x = ret - (cz / 2 + 1);
	  	b[i].y = cz / 2 + 1;
	  } 
	  else {
	   	b[i].x = ret - cz / 2;
	  	b[i].y = (-1) * cz / 2;
	  }
	}
	if(val == cs + (ret - 1) * 2 + 1) b[i].x = 0, b[i].y = ret;
	int fx = cs + (ret - 1) * 2 + 1;
	if(val >= fx + 1 && val <= fx + ret) {
	   b[i].x = (-1) * (val - fx);
	   b[i].y = b[i].x + ret;
	}
	fx = fx + ret;
	if(val >= fx + 1 && val <= fx + (ret - 1)) {
		b[i].y = (val - fx) * (-1);
		b[i].x = (-ret) - b[i].y; 
	}
	if(val == fx + ret) {
		b[i].x = 0, b[i].y = (-1) * ret;
	}
  }
  for (int i = 1; i <= n; i++) cout<<a[i]<<"\n";
  for (int i = 1; i <= m; i++) cout<<b[i].x<<" "<<b[i].y<<"\n";
  return 0;
}

T3 P=NP

solution

稍微把那个取最大值的条件转化一下，其实就是一种颜色只能取一次最大值。

有一个朴素的状压 dp：对于每个点 \(i\) 和集合 \(S\)，\(dp[i][S]\) 代表到达 \(i\)，在 \(S\) 中的点取过颜色，得到的最大路径长度。转移就是对于每条边 \(u\to v\)，分别考虑要不要取 \(v\) 的权值。如果要取，那么必须之前没取过，也就是对于不包含 \(c_v\) 的集合 \(S\) 有 \(dp[v][S\cup\{c_v\}]\leftarrow dp[u][S]+a_v\)。如果不取就随意了，转移是 \(dp[v][S]\leftarrow dp[u][S]\)。这样复杂度是 \(m2^n\)​。

然后你发现，如果一种颜色只出现了一次，显然没必要放到状压里，无脑取就行了

于是你只需要记出现至少两次的点，最多有 \(\frac n2\) 个。然后就做完了……时间复杂度 \(m2^{n/2}\)

code

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int read() {
 int x = 0, f = 1; char c = getchar();
 while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
 while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
 return x * f;
}
int n, m, cnt[40], f[37][(1 << 18)], id[40], tot, val[40], col[40];
vector<int>e[40];
int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    col[i] = read(), val[i] = read();
    cnt[col[i]]++;
    if(cnt[col[i]] == 2) id[col[i]] = ++tot;
  }
  m = read();
  for (int i = 1; i <= m; i++) {
    int u = read(), v = read();
    e[v].push_back(u);
  }
  memset(f, -0x3f, sizeof f);
  if(cnt[col[1]] == 1) f[1][0] = val[1];
  else {
    f[1][(1 << (id[col[1]] - 1))] = val[1];
    f[1][0] = 0;
  }
  for (int i = 2; i <= n; i++) {
    for (int k = 0; k < e[i].size(); k++) {
       int j = e[i][k];
       for (int S = 0; S < 1 << tot; S++) {
         if(cnt[col[i]] == 1) f[i][S] = max(f[i][S], f[j][S] + val[i]);
         else {
           f[i][S] = max(f[i][S], f[j][S]);
           int M = S | (1 << id[col[i]] - 1);
           if(!(S & (1 << id[col[i]] - 1))) f[i][M] = max(f[i][M], f[j][S] + val[i]);
         }
       }
    }
  }
  for (int i = 1; i <= n; i++) {
    int ans = *max_element(f[i], f[i] + (1 << tot));
    if(ans < 0) ans = 0;
    cout<<ans<<"\n";
  }
  system("pause");
  return 0;
}

T4 后缀数组

solution

考虑 SA 中相邻的元素，也就是排名相邻的两个串。如果你知道 Height，相当于你就知道了 \(h_i\) 对字符的相等关系，和末尾一对字符的小于关系。对于相等关系，可以用并查集合并。

如果你不知道 Height，那也可以通过判断它后面的字符串的大小关系确定能不能相等。即，对于后缀 \(x,y\)，\(x\) 的字典序小于 \(y\)。如果 \(x+1\) 字典序小于 \(y+1\)，那么 \(x,y\) 位置的字符可以取等，否则必须 \(s_x<s_y\)。判断 \(x+1,y+1\) 的字典序可以通过求 SA 的逆数组得到。

然后把这些小于关系在并查集合并后的点上连边，那实际上就是找一个字典序最小拓扑序。可以按照 SA 的顺序贪心，每个合并后的点放能放的最小值，这样一定是字典序最小的（因为每个字符都是最小的）

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
 
const int MAXn = 5005;
int sa[MAXn], hei[MAXn], rk[MAXn], val[MAXn];
 
 
int g[MAXn];
int f(int x) {
    return g[x] = (g[x] == x ? x : f(g[x]));
}
void mg(int a, int b) {
    a = f(a), b = f(b);
    g[a] = b;
}
 
vector<int> v[MAXn];
 
void add(int x, int y) {
    // x < y
    v[y].pb(x);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> sa[i], rk[sa[i]] = i;
    for (int i = 1; i < n; i++)
        cin >> hei[i];
    for (int i = 1; i <= n + 1; i++)
        g[i] = i;
    rk[n + 1] = 0;
    for (int i = 1; i < n; i++) {
        if (hei[i] != -1) {
            for (int j = 0; j < hei[i]; j++)
                mg(sa[i] + j, sa[i + 1] + j);
        }
    }
 
    for (int i = 1; i < n; i++) {
        if (hei[i] != -1) {
            add(f(sa[i] + hei[i]), f(sa[i + 1] + hei[i]));
        }
        if (rk[sa[i] + 1] > rk[sa[i + 1] + 1])
            add(f(sa[i]), f(sa[i + 1]));
    } 
    val[n + 1] = -1;
    for (int i = 1; i <= n; i++)
        val[i] = -2;
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        int t = f(sa[i]);
        if (val[t] != -2) {
            assert(val[t] == cur);    
            continue;
        }
        for (ll x : v[t]) {
            assert(val[x] != -2);
            cur = max(cur, val[x] + 1);
        }
        assert(cur < 26);
        val[t] = cur;
    }
    for (int i = 1; i <= n; i++)
        cout << (char)('a' + val[f(i)]);
    cout << endl;
}
这篇关于11, 7 题解报告的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航