模拟。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public static void solve () { int n = io.nextInt(); int [] s = new int [n]; int [] e = new int [n]; for (int i = 0 ; i < n; i++) { s[i] = io.nextInt(); e[i] = io.nextInt(); } for (int i = 1 ; i < n; i++) { if (s[i] >= s[0 ] && e[i] >= e[0 ]) { io.println(-1 ); return ; } } io.println(s[0 ]); }
有两种情况,每行都放一个或者每列都放一个,然后模拟即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public static void solve () { int n = io.nextInt(); int [] a = new int [n]; int [] b = new int [n]; long suma = 0L ; int mina = Integer.MAX_VALUE; for (int i = 0 ; i < n; i++) { a[i] = io.nextInt(); suma += a[i]; mina = Math.min(mina, a[i]); } long sumb = 0L ; int minb = Integer.MAX_VALUE; for (int i = 0 ; i < n; i++) { b[i] = io.nextInt(); sumb += b[i]; minb = Math.min(minb, b[i]); } io.println(Math.min(suma + (long ) minb * n, sumb + (long ) mina * n)); }
所有连续重复数的个数就是最少操作次数,然后就是简单的应用组合数学。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 private static final int MOD = 998244353 ;public static void solve () { char [] s = io.next().toCharArray(); int n = s.length; long cnt = n, sum = 1L ; for (int i = 0 ; i < n; ) { int j = i + 1 ; while (j < n && s[j] == s[j - 1 ]) { j++; } sum = sum * (j - i) % MOD; cnt--; i = j; } for (long i = 1 ; i <= cnt; i++) { sum = sum * i % MOD; } io.println(cnt + " " + sum); }
固定右端点,然后分别考虑每一位,计算答案,公式如下:
$$
\sum_{r=1}^{n}\sum_{l=1}^{r}f(l,r)\cdot (r-l+1)
=\sum_{r=1}^{n}\sum_{i=0}^{31}\sum_{l=1}^{r}(f_{i}(1,r)\oplus f_{i}(1,l-1))\cdot (r-(l-1))
$$
可以发现对于每一位,\(f_{i}(1,r)\oplus f_{i}(1,l-1)\) 的值不是 \(1\) 就是 \(0\),只有当值为 \(1\) 时才会对答案有贡献。如果 \(f_{i}(1,r)=1\),那么右端点 \(r\) 的第 \(i\) 位对答案的贡献为 \((cnt[i][0]\cdot r-sum[i][0])\cdot 2^{i}\)(其中 \(cnt[i][0]\) 表示前缀中 \(f_{i}=0\) 的个数,\(sum[i][0]\) 表示前缀中 \(f_{i}=0\) 的区间长度之和),另一种情况同理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 private static final int MOD = 998244353 ;public static void solve () { int n = io.nextInt(); int [] s = new int [n + 1 ]; for (int i = 0 ; i < n; i++) { s[i + 1 ] = s[i] ^ io.nextInt(); } long ans = 0L ; long [][] cnt = new long [32 ][2 ]; long [][] sum = new long [32 ][2 ]; for (int i = 0 ; i <= n; i++) { for (int j = 0 ; j < 32 ; j++) { int x = s[i] >> j & 1 ; ans = (ans + (cnt[j][x ^ 1 ] * i - sum[j][x ^ 1 ]) % MOD * (1 << j)) % MOD; cnt[j][x]++; sum[j][x] += i; } } io.println(ans); }