|
1.Mod, Or and Everything
简单结论题，打表找规律。
题目大意：现在给你一个数，你要把(n%1) | (n%2) | … | (n%n)计算出来。
思路：首先我们打表找一下规律，发现就是从1到x做或操作，其中当n是奇数时x为(n/2)，当n是偶数时x为（n/2 - 1）。观察数据我们会发现n是1e12，一半就是5e11，很明显暴力在1s的时间会爆。所以我们再观察一下。要注意的是这是二进制的运算，我们把目光投到二进制上，发现这样的一个运算得到的是1111这样的数。好的到这里就可以了。
代码：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ctx cout << "xxxxx" << endl
#define inf 0x3f3f3f3f
#define eps 0.000000001
#define forn for(int i = 1; i <= n; i++)
#define ct1 cout << -1 << endl;
const int INF = 0x3f3f3f3f;
const double pai = acos(-1.0);
int main() {
int t;
cin >> t;
while(t--) {
ll n;
cin >> n;
ll tmp = 0;
if(n & 1) {
tmp = n/2;
} else {
tmp = n/2 - 1;
}
vector<ll> tt;
while(tmp) {
tt.push_back(tmp%2);
tmp /= 2;
}
ll ans = 1;
for(int i = 1; i <= tt.size(); i++){
ans *= 2;
}
cout << ans - 1 << endl;
}
}
5.Minimum spanning tree
结论题
题目大意：
给你一个数n，现在你会有从2到(n-1)的点，让他们两两相连。然后每条边的权值就是两个数的最小公倍数。
思路：
我们先思考到偶数，所有偶数与二相连就是他们本身，然后看到奇数，奇数中有两种数，一种是质数，另一种是非质数。我们看到非质数，他们如果与自己的除数相连，那就是本身。现在就剩下质数，我们把他们与质数相连，就能得到最小的2*质数。现在结论就出来了，从3加到n，然后遇到质数就加上这个质数。
代码：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ctx cout << "xxxxx" << endl
#define inf 0x3f3f3f3f
#define int long long
#define eps 0.000000001
#define forn for(int i = 1; i <= n; i++)
#define ct1 cout << -1 << endl;
const int INF = 0x3f3f3f3f;
const double pai = acos(-1.0);
const int maxn = 1e7 + 10;
bool book[maxn];
signed main(){
for(int i = 2; i <= 1e7; i++){
if(!book[i]){
for(int j = 2; i*j <= 1e7 + 10; j++){
book[i*j] = 1;
}
}
}
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int ans = (n+3)*(n-2)/2;
for(int i = 3; i <= n; i++){
if(!book[i]) ans += i;
}
cout << ans << endl;
}
}
8.Maximal submatrix
单调栈或者悬线法，我不会。
在做本题前请要看一下：单调栈做法基础
题目大意：要在每一列找一个不递减的一段，然后合并，得到面积最大的矩形。
思路：我们每一列分开看，每一列的元素都转换成是否比上一个元素大。这样，每一列复杂的元素就变得简单起来，也可以说，那个元素表示的是当前的高度，不懂的可以自己画图观察，起点不一样是不会影响整个值的。然后对每一行都来一次寻找矩形最大面积的处理。然后取最值。
代码：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#define ctx cout << "xxxxxx" << endl
using namespace std;
using ll = long long;
int n, m;
const int maxn = 2e3 + 10;
struct vv {
int val, idx;
};
int b[maxn][maxn];
vv a[maxn][maxn];
void solve() {
cin >> n >> m;
for(int i = 1; i <= n+1; i++){
for(int j = 1; j <= m+1; j++){
b[i][j] = 0;
a[i][j].val = 0, a[i][j].idx = 0;
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> b[i][j];
}
}
for(int i = n; i >= 1; i--) {
for(int j = m; j >= 1; j--) {
if(b[i][j] <= b[i+1][j]) {
a[i][j].val = a[i+1][j].val + 1;
} else {
a[i][j].val = 1;
}
a[i][j].idx = j;
}
}
stack<vv> sk;
sk.push({0,0});
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m+1; j++){
while((sk.top()).val > a[i][j].val){
vv tmp = (sk).top();
sk.pop();
ans = max(ans, tmp.val * (j - tmp.idx));
}
sk.push(a[i][j]);
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--) {
solve();
}
}
9.KD-Graph
据说是签到题，最小生成树。
题目大意：我们现在有n个点和m条边，现在我们要把他们分成k个部分，满足：
- 每个部分至少一个点。
- 如果顶点p和q（p≠ q）在同一组中，p和q之间必须至少有一条路径满足此路径中的最大值小于或等于D
- 如果顶点p和q（p≠ q）在不同的组中，p和q之间不能有任何路径满足此路径中的最大值小于或等于D
思路：把边权从小到大排序，然后并查集合并。有k个部分就可以找到，并且当前合并的就是最小的D。然后你必须把边权相同的都放进去。
官方题解是一开始看作n个部分，然后合并的过程中就可以减少部分的数。然后一个大部分看作一个部分，其余点都是分别做一个部分。这样这满足题意了。当然，据说能用最小生成树做。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ctx cout << "xxxxx" << endl
#define inf 0x3f3f3f3f
#define int long long
#define eps 0.000000001
#define forn for(int i = 1; i <= n; i++)
#define ct1 cout << -1 << endl;
const int INF = 0x3f3f3f3f;
const double pai = acos(-1.0);
const int maxn = 1e6 + 10;
int fa[maxn];
inline void iit(int n) {
for (int i = 0; i <= n; i++) fa[i] = i;
}
int findx(int x) {
return (x == fa[x] ? x : (fa[x] = findx(fa[x])));
}
void merge(int x, int y) {
int f_x = findx(x), f_y = findx(y);
if (f_x != f_y) {
fa[f_x] = f_y;
}
}
struct vv {
int u, v, w;
}p[maxn];
bool cmp(vv a, vv b) {
return a.w < b.w;
}
void solve() {
int n, m, k, now, ans;
cin >> n >> m >> k;
now = n, ans = 0;
iit(n);
for (int i = 1; i <= m; i++) {
cin >> p[i].u >> p[i].v >> p[i].w;
}
sort(p + 1, p + 1 + n, cmp);
for (int i = 1; i <= m; i++) {
if (p[i].w != p[i - 1].w) {
if (now == k)
{
cout << ans << endl;
return;
}
}
int c = findx(p[i].u), d = findx(p[i].v);
if (c == d) continue;
now--;
merge(c, d);
ans = p[i].w;
}
cout << (now == k ? ans : -1) << endl;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
}
|