A 签到题

注意字符必须改变,有(ab, xy)肯定是不行的

B 填数+规律

题意

在$n\times n$的网格中填数,先1~ceil(n*n/2)顺序填(x+y)是偶数的格子,在填(x+y)是奇数的格子 例如n=4, n=5的情况 示例

做法一:分类讨论

按(x+y)奇偶讨论是否加上右下角的值,再讨论x,y的奇偶

做法二:规律

(x+y)是偶数的位置的值全部减去右下角的值会发现其实也是1~ceil(n*n/2)的填数 对于这种情况其值为$\displaystyle n\frac{x-1}{2}+\frac{y+1}{2}$

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define clr(a, b) memset(a,b,sizeof(a))
#ifdef __LOCAL_DEBUG__
#define _debug(fmt,...)fprintf(stderr,"\033[94m%s: " fmt "\n\033[0m",__func__,##__VA_ARGS__)
#define dg(a) cout <<"\033[94m" <<#a << "\033[0m = "<< a << endl;
#else
#define _debug(...) ((void)0)
#define dg(a)((void)0)
#endif
 
typedef long long ll;
typedef long double ld;
const ld pi = acos(-1);
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = static_cast<int>(1e6 + 7);
 
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n, q;
    cin >> n >> q;
    while (q--) {
        ll x, y;
        cin >> x >> y;
        ll fst = (n * n + 1) / 2;
        // 做法一
        ll ans = 0;
        if ((x + y) & 1) {
            if (x & 1) ans = fst + x / 2 * n + y / 2; // 奇偶
            else ans = fst + (x / 2 - 1) * n + n / 2 + (y + 1) / 2; // 偶奇
        } else {
            if (x & 1) ans = x / 2 * n + (y + 1) / 2; // 奇奇
            else ans = (x / 2 - 1) * n + (n + 1) / 2 + y / 2; // 偶偶
        }
        // 做法二
        ans = n * (x - 1) / 2 + (y + 1) / 2 + ((x + y) % 2 ? fst : 0);
        cout << ans << endl;
    }
}

C 签到题

给出序列你需要找到四个数字组成矩形, 并且最小化$\displaystyle \frac{P^2}{S}$, 其中P是周长,S是面积 $nlog(n)+O(n)$ 排序扫一遍, 最小化$\displaystyle \frac{a}{b}+\frac{b}{a}$即可

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>

using namespace std;
#define clr(a, b) memset(a,b,sizeof(a))

#ifdef __LOCAL_DEBUG__
#define _debug(fmt,...)fprintf(stderr,"\033[94m%s: " fmt "\n\033[0m",__func__,##__VA_ARGS__)
#define dg(a) cout <<"\033[94m" <<#a << "\033[0m = "<< a << endl;
#define dgloop(v) {for(auto x:v) cout <<"\033[94m"<<x<<"\033[0m ";cout<<endl;}
#else
#define _debug(...) ((void)0)
#define dg(a)((void)0)
#define dgloop(v)((void)0)
#endif

const int mod = 1e9 + 7;
const int maxn = static_cast<int>(1e6 + 7);
const int maxm = 1e4 + 7;
int a[maxn];
int vis[maxm];

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        clr(vis, 0);
        vector<int> v;
        int flag = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            vis[a[i]]++;
            if (vis[a[i]] % 2 == 0) v.push_back(a[i]);
            if (vis[a[i]] % 4 == 0) flag = a[i];
        }
        if (v.size() == 2) {
            cout << v[0] << " " << v[0] << " " << v[1] << " " << v[1] << endl;
            continue;
        } else if (flag) {
            cout << flag << " " << flag << " " << flag << " " << flag << endl;
            continue;
        }
        sort(v.begin(), v.end()); dgloop(v);
        int p1, p2;
        double MIN = 1e20;
        for (int i = 0; i < v.size() - 1; i++) {
            if (1.0 * v[i] / v[i + 1] + 1.0 * v[i + 1] / v[i] < MIN) {
                MIN = 1.0 * v[i] / v[i + 1] + 1.0 * v[i + 1] / v[i];
                p1 = v[i], p2 = v[i + 1];
            }
        }
        cout << p1 << " " << p1 << " " << p2 << " " << p2 << endl;
    }
}

D