Team Contests - Warmup

题意：...

思路：不会

代码：...

随机 B

题意：给n个点，问是否有一个圆上有最少n/3个点

思路：随机大法好。

代码：...

递推 C

题意：对自然数列{1,2,3,4,5,6...}进行n次操作，每次操作有一个x，意思是前x个保留，后x个删去，再x个保留，后x个删去。。。形成新的序列，问n次操作后第n个数字。

思路：（bh）我开始想二分答案，但是对于n次过程中就被删去的点就无法处理了。那么倒过来做就很方便，已知最后的位置是第n个，那么在第n次操作前的位置应该是 $n'=n+(n/a_i-f)*a_i$ ，所以倒过来 $O(n)$ 就做好了。结果可能爆long long，用Java写大数。

关键：逆序

代码：

import java.math.*;

import java.io.*;

import java.util.*;

public class Main {

	static int[] a;

	public static void main(String[] args) {

		Scanner in = new Scanner (new BufferedInputStream (System.in));

		int T = in.nextInt ();

		for (int cas=1; cas<=T; ++cas) {

			int n = in.nextInt ();

			a = new int[10005];

			for (int i=1; i<=n; ++i) {

				a[i] = in.nextInt ();

			}

			BigInteger ans = BigInteger.valueOf(n);

			for (int i=n; i>=1; --i) {

				int f = 0;

				if(ans.mod(BigInteger.valueOf(a[i])).compareTo(BigInteger.ZERO) == 0) {

					f = 1;

				}

				BigInteger tmp = ans.divide(BigInteger.valueOf(a[i])).subtract(BigInteger.valueOf(f)).multiply(BigInteger.valueOf(a[i]));

				ans = ans.add(tmp);

			}

			System.out.println (ans);

		}

	}

}

模拟 D

题意：炉石游戏

思路：坑。。。

代码：...

题意：麻将

思路：...

代码：...

离散化 F

题意：平面上有n个点，问有多少个不同位置的矩形，满足矩形四条边上的都正好有m个点。

思路：（bh）对点进行坐标离散化点归类，先从左上角开始找到在X容器里，按照y坐标排序后的前(m-1)个点，也就是左下角，同理可以找到右上角，然后从左下角和右上角出发去找右下角，看看是否重合，如果重合表示满足条件，计数即可。

代码：

ans1：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m;

struct Point {

    int x, y, id;

}p[N];

struct Node {

    int v, id;

    bool operator < (const Node &rhs) const {

        return v < rhs.v;

    }

};

std::vector<Node> X[N], Y[N];

int xs[N], ys[N];

int totx, toty;

int solve() {

    sort (xs, xs+totx);

    totx = unique (xs, xs+totx) - xs;

    sort (ys, ys+toty);

    toty = unique (ys, ys+toty) - ys;

    for (int i=0; i<totx; ++i) {

        X[i].clear ();

    }

    for (int i=0; i<toty; ++i) {

        Y[i].clear ();

    }

    for (int i=1; i<=n; ++i) {

        int px = lower_bound (xs, xs+totx, p[i].x) - xs;

        int py = lower_bound (ys, ys+toty, p[i].y) - ys;

        X[px].push_back ((Node) {p[i].y, p[i].id});

        Y[py].push_back ((Node) {p[i].x, p[i].id});

    }

    for (int i=0; i<totx; ++i) {

        sort (X[i].begin (), X[i].end ());

    }

    for (int i=0; i<toty; ++i) {

        sort (Y[i].begin (), Y[i].end ());

    }

    int ret = 0;

    for (int i=1; i<=n; ++i) {

        Node tmp1 = (Node) {p[i].y, p[i].id};

        int px = lower_bound (xs, xs+totx, p[i].x) - xs;

        int vpx = lower_bound (X[px].begin (), X[px].end (), tmp1) - X[px].begin ();

        if (vpx - m + 1 < 0) continue;

        int vpx1 = vpx - m + 1;

        int ty = X[px][vpx1].v;  //(p[i].x, ty)

        Node tmp3 = (Node) {p[i].x, p[i].id};

        int pyt = lower_bound (ys, ys+toty, ty) - ys;

        int vpyt = lower_bound (Y[pyt].begin (), Y[pyt].end (), tmp3) - Y[pyt].begin ();

        if (vpyt + m - 1 >= Y[pyt].size ()) continue;

        int vpyt2 = vpyt + m - 1;

        int x = Y[pyt][vpyt2].v, y = ty;

        Node tmp2 = (Node) {p[i].x, p[i].id};

        int py = lower_bound (ys, ys+toty, p[i].y) - ys;

        int vpy = lower_bound (Y[py].begin (), Y[py].end (), tmp2) - Y[py].begin ();

        if (vpy + m - 1 >= Y[py].size ()) continue;

        int vpy2 = vpy + m - 1;

        int tx = Y[py][vpy2].v;  //(tx, p[i].y)

        Node tmp4 = (Node) {p[i].y, p[i].id};

        int pxt = lower_bound (xs, xs+totx, tx) - xs; //now

        int vpxt = lower_bound (X[pxt].begin (), X[pxt].end (), tmp4) - X[pxt].begin ();

        if (vpxt - m + 1 < 0) continue;

        int vpxt2 = vpxt - m + 1;

        int x2 = tx, y2 = X[pxt][vpxt2].v;

        if (x == x2 && y == y2) {

            ret++;

        }

    }

    return ret;

}

int main() {

    int T;

    scanf ("%d", &T);

    while (T--) {

        scanf ("%d%d", &n, &m);

        totx = toty = 0;

        for (int i=1; i<=n; ++i) {

            scanf ("%d%d", &p[i].x, &p[i].y);

            p[i].id = i;

            xs[totx++] = p[i].x;

            ys[toty++] = p[i].y;

        }

        printf ("%d\n", solve ());

    }

    return 0;

}

ans2（zcj）

#include<bits/stdc++.h>

#define mk make_pair

using namespace std;

typedef long long LL;

const int maxn =  + ;

int n, m;

pair<int, int> xx[maxn];

vector<LL> v;

vector<int> x[maxn];

vector<int> y[maxn];

map<pair<int, int>, int> p;

int len;

void solve(){

    int cnt = ;

    for (int i = ; i < n; i++){

        if (m <= ) break;

        int tx = xx[i].first;

        int ty = xx[i].second;

        int lenx = x[tx].size(); //表示里面有几个y

        int leny = y[ty].size();//表示里面有几个x

        if (lenx < m) continue;

        if (leny < m) continue;

        //先找x上方的m-1个，里面放着y

        int py = lower_bound(x[tx].begin(), x[tx].end(), ty) - x[tx].begin();//在x的集合里面，y的位置

        if (py + m > lenx) continue;

        int px = lower_bound(y[ty].begin(), y[ty].end(), tx) - y[ty].begin();//在y这个集合里面，x的位置

        if (px + m > leny) continue;

        int posx = y[ty][px + m - ];

        int posy = x[tx][py + m - ];//this?

        if (p[mk(posx, posy)]){

            cnt++;

        }

    }

    printf("%d\n", cnt);

}

int main(){

    int t; cin >> t;

    while (t--){

        scanf("%d%d", &n, &m);

        for (int i = ; i < n; i++){

            LL a, b;

            scanf("%I64d%I64d", &a, &b);

            xx[i] = mk(a, b);

            v.push_back(a);

            v.push_back(b);

        }

        sort(v.begin(), v.end());

        v.erase(unique(v.begin(), v.end()), v.end());

        int lx = , ly = ;

        for (int i = ; i < n; i++){

            int tx = xx[i].first = lower_bound(v.begin(), v.end(), xx[i].first) - v.begin();

            int ty = xx[i].second = lower_bound(v.begin(), v.end(), xx[i].second) - v.begin();

            //printf("%d %d\n", xx[i].first, xx[i].second);

            p[mk(tx, ty)] = ;

            x[tx].push_back(ty);

            y[ty].push_back(tx);

            lx = max(lx, tx);

            ly = max(ly, ty);

        }

        for (int i = ; i <= lx; i++){

            sort(x[i].begin(), x[i].end());

        }

        for (int i = ; i <= ly; i++){

            sort(y[i].begin(), y[i].end());

        }

        solve();

        //初始化

        p.clear();

        v.clear();

        for (int i = ; i <= lx; i++){

            x[i].clear();

        }

        for (int i = ; i <= ly; i++){

            y[i].clear();

        }

        memset(xx, , sizeof(xx));

    }

    return ;

}

题意：问[L, R]有多个数字的所有数位相加和是素数的个数。

思路：（bh）数位DP即可，写太着急，long long写成int。。。

代码：

#include <bits/stdc++.h>

typedef long long ll;

bool is_prime(int x) {

    if (x < 2) return false;

    if (x == 2 || x == 3) return true;

    if (x % 6 != 1 && x % 6 != 5) return false;

    for (int i=5; i*i<=x; i+=6) {

        if (x % i == 0 || x % (i + 2) == 0) return false;

    }

    return x != 1;

}

ll dp[20][10][200];

int bit[20];

ll DFS(int pos, int pre, int sum, bool limit) {

    if (pos == -1) {

        return is_prime (sum);

    }

    ll now = dp[pos][pre][sum];

    if (now != -1 && !limit) {

        return now;

    }

    ll ret = 0;

    int d = limit ? bit[pos] : 9;

    for (int i=0; i<=d; ++i) {

        ret += DFS (pos - 1, i, sum + i, limit && i == d);

    }

    if (!limit) {

        dp[pos][pre][sum] = ret;

    }

    return ret;

}

ll solve(ll n) {

    if (n <= 0) {

        return 0;

    }

    int c = 0;

    for (; n>0; n/=10) bit[c++] = n % 10;

    return DFS (c - 1, 0, 0, true);

}

int main() {

    memset (dp, -1, sizeof (dp));

    int T;

    scanf ("%d", &T);

    while (T--) {

        ll a, b;

        scanf ("%I64d%I64d", &a, &b);

        printf ("%I64d\n", solve (b) - solve (a - 1));

    }

    return 0;

}

题意：税收

思路：...

代码：...

题意：图论

思路：...

代码：...

巴特西

Team Contests - Warmup（2016年多校热身赛，2016年黑龙江省赛）

Team Contests - Warmup

最新文章

热门文章