A 元宵节的奇怪灯谜
这是一个普通的模拟题，把数字以字符串的形式进行读入，否则会因为数据范围超过int/long导致数据溢出。读入字符串之后，其实就可以对字符串从后往前处理。处理的方法按照题目中所述就可以了。
Cpp
#include <iostream>
using namespace std;
string str;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> str;
for (int i = str.size() - 1; i >= 0; i--)
{
int x = str[i] - '0';
x = (x * 2 % 9 + 1) % 9 + 1;
// x = x * 2;
// if(x > 9) x -= 9;
// x += 2;
// if(x > 9) x -= 9;
cout << x;
}
return 0;
}
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int len = str.length();
for (int i = len - 1; i >= 0; i--) {
int x = str.charAt(i) - '0';
x = (x * 2 % 9 + 1) % 9 + 1;
System.out.print(x);
}
sc.close();
}
}
Python
nums = []
str_input = input()
for i in range(len(str_input)):
x = int(str_input[i])
x = (x * 2 % 9 + 1) % 9 + 1
nums.append(x)
for i in range(len(nums) - 1, -1, -1):
print(nums[i], end='')
B 友谊的聚餐
同学们之前的相互关系，可以使用并查集把他们划归为同一桌。然后，使用map来记录每桌有多少人，map的大小即为桌子的数量。
Cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3;
int n, m, f[N];
map<int, int> mp;
// 并查集模板
int find(int x)
{
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int i;
cin >> n >> m;
// 并查集需要的初始化
for(i = 1; i <= n; ++i) f[i] = i;
for(i = 1; i <= m; ++i)
{
int x, y;
cin >> x >> y;
f[find(x)] = f[find(y)];
}
// 记录每个人属于哪一桌
for(i = 1; i <= n; ++i) mp[find(i)]++;
int cnt = 0, mxSZ = 0;
// 遍历桌子找最大人数
for(auto x : mp)
{
cnt++;
mxSZ = max(mxSZ, x.second);
}
// 注意输出格式
cout << cnt << '\n' << mxSZ;
}
Java
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
static int[] f;
static Map<Integer, Integer> mp;
static int find(int x) {
if (x != f[x]) f[x] = find(f[x]);
return f[x];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
f = new int[n + 1];
mp = new HashMap<>();
for (int i = 1; i <= n; ++i) f[i] = i;
for (int i = 1; i <= m; ++i) {
int x = scanner.nextInt();
int y = scanner.nextInt();
f[find(x)] = f[find(y)];
}
for (int i = 1; i <= n; ++i) mp.put(find(i), mp.getOrDefault(find(i), 0) + 1);
int cnt = 0, mxSZ = 0;
for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
cnt++;
mxSZ = Math.max(mxSZ, entry.getValue());
}
System.out.println(cnt + "\n" + mxSZ);
}
}
Python
def find(x):
if x != f[x]:
f[x] = find(f[x])
return f[x]
n, m = map(int, input().split())
f = list(range(n + 1))
mp = {}
for _ in range(m):
x, y = map(int, input().split())
f[find(x)] = f[find(y)]
for i in range(1, n + 1):
mp[find(i)] = mp.get(find(i), 0) + 1
cnt = 0
mxSZ = 0
for value in mp.values():
cnt += 1
mxSZ = max(mxSZ, value)
print(cnt)
print(mxSZ)
C 这次能获得爱情吗
这题其实是一个图论中求最短路径的题。题中所构造出来的是一个 n * m 的矩形，每一个格子可以看作图的一个结点，在每个结点只能向上下左右四个方向移动。
注意
初始化dist数组时，把数组全部置为 LLONG_MAX ，Java里则需要置为 Long.MAX_VALUE ，否则由于 1 ≤ n * m ≤ 2e5 、0 ≤ a ≤ 1e8，难免会出现有些路径计算超过 int 最大范围的情况。
Cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, h;
vector<vector<int>> arr, vis;
vector<vector<ll>> dist;
// 定义好四个方向,方便后续遍历每个结点的路径
int dire[4][2] = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
class Node
{
public:
int x, y;
ll val;
bool operator<(const Node &other) const
{
return val < other.val;
}
bool operator>(const Node &other) const
{
return val > other.val;
}
};
priority_queue<Node, vector<Node>, greater<Node>> heap;
void dij(int x0, int y0)
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
dist[i][j] = LLONG_MAX;
vis[i][j] = 0;
}
}
dist[x0][y0] = 0;
heap.push({x0, y0, 0});
while (!heap.empty())
{
auto t = heap.top();
heap.pop();
int dis = t.val;
if (vis[t.x][t.y])
continue;
vis[t.x][t.y] = 1;
for (int i = 0; i < 4; ++i)
{
int xt = t.x + dire[i][0], yt = t.y + dire[i][1];
// 判断是否超出矩形范围
if (xt >= 1 && xt <= n && yt >= 1 && yt <= m)
{
// 找到更短路径进行更新
if (arr[xt][yt] + dist[t.x][t.y] < dist[xt][yt])
{
dist[xt][yt] = arr[xt][yt] + dist[t.x][t.y];
heap.push({xt, yt, dist[xt][yt]});
}
}
}
}
}
void solve()
{
cin >> n >> m;
arr.resize(n + 1);
vis.resize(n + 1);
dist.resize(n + 1);
for(int i = 1; i <= n; ++i)
arr[i].resize(m + 1), vis[i].resize(m + 1), dist[i].resize(m + 1);
int x0, y0, x1, y1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; ++j)
cin >> arr[i][j];
cin >> x0 >> y0 >> x1 >> y1;
dij(x0, y0);
cout << dist[x1][y1] << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
}
Java
import java.io.*;
import java.util.PriorityQueue;
public class Main {
static int n, m, x0, y0, x1, y1;
static boolean[][] vis;
static long[][] arr, dist;
static PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
static int[][] dire = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static void main(String[] args) {
Scanner sc = new Scanner();
n = sc.nextInt();
m = sc.nextInt();
arr = new long[n + 1][m + 1];
dist = new long[n + 1][m + 1];
vis = new boolean[n + 1][m + 1];
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
arr[i][j] = sc.nextLong();
dist[i][j] = Long.MAX_VALUE;
}
}
x0 = sc.nextInt();
y0 = sc.nextInt();
x1 = sc.nextInt();
y1 = sc.nextInt();
dij(x0, y0);
System.out.println(dist[x1][y1]);
}
static void dij(int x, int y) {
dist[x][y] = 0;
priorityQueue.add(new Node(x, y, 0));
while (!priorityQueue.isEmpty()) {
Node now = priorityQueue.poll();
if (vis[now.x][now.y]) continue;
vis[now.x][now.y] = true;
for(int i = 0; i < 4; ++i) {
int tx = now.x + dire[i][0];
int ty = now.y + dire[i][1];
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m) {
if(dist[tx][ty] > dist[now.x][now.y] + arr[tx][ty]) {
dist[tx][ty] = dist[now.x][now.y] + arr[tx][ty];
priorityQueue.add(new Node(tx, ty, dist[tx][ty]));
}
}
}
}
}
}
class Scanner {
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public int nextInt() {
try {
st.nextToken();
} catch (IOException e) {
throw new RuntimeException(e);
}
return (int) st.nval;
}
public long nextLong() {
try {
st.nextToken();
} catch (IOException e) {
throw new RuntimeException(e);
}
return (long) st.nval;
}
}
class Node implements Comparable<Node> {
public int x, y;
public long val;
public Node(int x, int y, long val) {
this.x = x;
this.y = y;
this.val = val;
}
@Override
public int compareTo(Node other) {
return Long.compare(this.val, other.val);
}
}
D 或许这才是爱情
策划的是一个 二维差分 + 二维前缀和。在前期对鲜花矩阵的处理中，会对一个区域范围内的鲜花造成影响，如果不使用差分数组，这里的最坏复杂度就是 O(tnm)。之后是计算这些鲜花矩阵中 一个长度为 l 的正方形矩阵鲜花鲜艳值的最大值，而如果不使用前缀和，此处可能就需要四层for循环处理。(这种代码，大家就可以去看下以提交的超时代码中去查看)。
注意
在求最大值之前，大家一般都会定义一个变量 res 来遍历求最大值。经过验题，以及场上选手提交的代码，很多人习惯性直接外部声明这个 res ，或者是把res初值设为 0 或 INT_MIN。然而根据此题的数据范围：1 ≤ t ≤ 1e5、1 ≤ a ≤ 1e5、-1e5 ≤ q ≤ 1e5，完全有可能最后这些鲜花矩阵的鲜艳值都是负数，而且是极小的负数，最小可达 -1e10。经过检查，造出来的数据中确实存在该情况数据。如果按照不严谨的初始化，在遇到该数据时，就会出错。
Cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
int n, m, l, t;
ll arr[N][N], brr[N][N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> l >> t;
int i, j;
for(i = 1; i <= n; ++i)
for(j = 1; j <= m; ++j)
cin >> arr[i][j];
while(t--)
{
int x1, y1, x2, y2;
ll q;
cin >> x1 >> y1 >> x2 >> y2 >> q;
brr[x1][y1] += q;
brr[x1][y2 + 1] -= q;
brr[x2 + 1][y1] -= q;
brr[x2 + 1][y2 + 1] += q;
}
// 二维差分方便计算t次操作
for(i = 1; i <= n; ++i)
for(j = 1; j<= m; ++j)
brr[i][j] += brr[i - 1][j] + brr[i][j - 1] - brr[i - 1][j - 1];
for(i = 1; i <= n; ++i)
for(j = 1; j<= m; ++j)
arr[i][j] += brr[i][j];
// 前缀和方便求最大矩阵
for(i = 1; i <= n; ++i)
for(j = 1; j <= m; ++j)
arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
ll res = LLONG_MIN;
for(i = 1; i + l - 1 <= n; ++i)
for(j = 1; j + l - 1 <= m; ++j)
{
int rx = i + l - 1, ry = j + l - 1;
res = max(res, arr[rx][ry] - arr[i - 1][ry] - arr[rx][j - 1] + arr[i - 1][j - 1]);
}
cout << res << '\n';
}
Java
import java.util.Scanner;
public class Main {
static final int N = 1005;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int l = scanner.nextInt();
int t = scanner.nextInt();
long[][] arr = new long[N][N];
long[][] brr = new long[N][N];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
arr[i][j] = scanner.nextLong();
}
}
while (t-- > 0) {
int x1 = scanner.nextInt();
int y1 = scanner.nextInt();
int x2 = scanner.nextInt();
int y2 = scanner.nextInt();
long q = scanner.nextLong();
brr[x1][y1] += q;
brr[x1][y2 + 1] -= q;
brr[x2 + 1][y1] -= q;
brr[x2 + 1][y2 + 1] += q;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
brr[i][j] += brr[i - 1][j] + brr[i][j - 1] - brr[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
arr[i][j] += brr[i][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
}
}
long res = Long.MIN_VALUE;
for (int i = 1; i + l - 1 <= n; ++i) {
for (int j = 1; j + l - 1 <= m; ++j) {
int rx = i + l - 1;
int ry = j + l - 1;
res = Math.max(res, arr[rx][ry] - arr[i - 1][ry] - arr[rx][j - 1] + arr[i - 1][j - 1]);
}
}
System.out.println(res);
}
}
E 探寻爱的真谛
标准的动态规划 01背包，不过此处有俩个约束条件“黑暗力量”和“狂暴因子”。按照01背包的做法去处理下即可。
注意
由于此处 1 ≤ G、V、N ≤ 1000，而如果使用没有降维的非滚动数组dp来做这道题时，声明dp数组时就会因为超过内存限制 WA掉。所以，切记使用滚动数组。
Cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int v, g, n;
int arr[N][3], f[N][N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> v >> g >> n;
int i, j, k;
for (i = 1; i <= n; ++i)
cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
for (i = 1; i <= n; ++i)
for (j = v; j >= arr[i][1]; --j)
for (k = g; k >= arr[i][2]; --k)
f[j][k] = max(f[j][k], f[j - arr[i][1]][k - arr[i][2]] + arr[i][0]);
cout << f[v][g];
return 0;
}
Java
import java.util.Scanner;
public class Main {
static final int N = 1005;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt();
int g = scanner.nextInt();
int n = scanner.nextInt();
int[][] arr = new int[N][3];
int[][] f = new int[N][N];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 3; ++j) {
arr[i][j] = scanner.nextInt();
}
}
for (int i = 1; i <= n; ++i) {
for (int j = v; j >= arr[i][1]; --j) {
for (int k = g; k >= arr[i][2]; --k) {
f[j][k] = Math.max(f[j][k], f[j - arr[i][1]][k - arr[i][2]] + arr[i][0]);
}
}
}
System.out.println(f[v][g]);
}
}
F 如梦初醒,终是没有爱情
一个子串想要能够经过重排成为一个回文串，区间内每个字母的个数要么全是偶数，要么只有一个字母出现的次数是奇数。
我们找个状态量记录这些字母出现次数的前缀。若在一个状态中，某个字母出现了奇数次/偶数次，那么减去这个状态上一次出现的情况，由于奇数 - 奇数会是一个偶数 并且 偶数 - 偶数得到的也是一个偶数，所以相减得到的一种情况就符合构成一个回文；而如果这个状态出现过 k 次，那么这个状态在当前位置就能有 k 种子串方案构回文。
Cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1 << 26;
int cnt[N];
void solve()
{
string s;
cin >> s;
int n = s.size();
ll ans = 0;
// 初始化,没有任何数出现过
cnt[0] = 1;
int sta = 0; // 记录当前前缀上的数出现次数的奇偶情况
for (int i = 0; i < n; ++i)
{
sta ^= 1 << (s[i] - 'a'); // 异或，即原先有奇数个,加上当前这一位就有偶数个了;反之偶数个加一个变成奇数个
ans += cnt[sta]; // 加上与当前状态各个数出现次数完全相同的方案数
for (int j = 0; j < 26; ++j) ans += cnt[sta ^ (1 << j)]; // 寻找与当前状态仅差一位的情况
// 当前状态出现次数增加
cnt[sta]++;
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
}
Java
import java.io.*;
public class Main {
static final int N = 1 << 26;
static int[] cnt = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner();
char[] chars = sc.next().toCharArray();
cnt[0] = 1;
int len = chars.length;
int sta = 0;
long res = 0;
for(int i = 0; i < len; ++i) {
sta ^= 1 << (chars[i] - 'a');
res += cnt[sta];
for(int j = 0; j < 26; ++j) {
res += cnt[sta ^ (1 << j)];
}
cnt[sta]++;
}
System.out.println(res);
}
}
class Scanner {
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public String next() {
try {
st.nextToken();
} catch (IOException e) {
throw new RuntimeException(e);
}
return st.sval;
}
}
京公网安备 11010502036488号