欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2017北京区域赛

程序员文章站 2024-01-15 23:56:22
...

https://www.cnblogs.com/31415926535x/p/11668631.html

模拟题场啊,,,,,

题目链接

E - Cats and Fish

签到题吧,,读完题后感觉是模拟,,然后写完之后一测样例wa了,,这时队友说推出公示了,,于是我就放弃调去看别的题了,,,但是wa了几发后又用模拟过的,,,

直接模拟时间,,记录每只猫的状态,,每次判断一下就行了,,,

#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(TM(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e3+ 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;

int a[maxn], n, m, x;
bool vis[maxn];
int TM[maxn];
int main()
{
    // double pp = clock();
    // freopen("233.in", "r", stdin);
    // freopen("233.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    while(cin >> m >> n >> x)
    {
        for(int i = 1; i <= n; ++i)cin >> a[i];
        for(int i = 1; i <= n; ++i)vis[i] = false;
        for(int i = 1; i <= n; ++i)TM[i] = 0;
        sort(a + 1, a + 1 + n);
        int all = 0;
        for(int t = 1; t <= x; ++t)
        {
            for(int i = 1; i <= n; ++i)
                if(!vis[i] && all < m)
                {
                    vis[i] = true;
                    ++all;
                }
            for(int i = 1; i <= n; ++i)if(vis[i])++TM[i];
            for(int i = 1; i <= n; ++i)
                if(vis[i])
                {
                    TM[i] %= a[i];
                    if(TM[i] == 0)vis[i] = false;
                }
        }
        int ans = 0;
        for(int i = 1; i <= n; ++i)if(vis[i])++ans;
        cout << m - all << " " << ans << endl;
    }

    // cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
    return 0;
}

F - Secret Poems

小模拟

#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(TM(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e3+ 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;

char s[maxn][maxn];
char str[maxn * maxn];
char t[maxn][maxn];
int main()
{
    // double pp = clock();
    // freopen("233.in", "r", stdin);
    // freopen("233.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    while(cin >> n)
    {
        for(int i = 1; i <= n; ++i)cin >> s[i] + 1;
        if(n == 1)
        {
            cout << s[1] + 1 << endl;
            continue;
        }
        int i = 1, j = 1, tot = 1;
        str[tot++] = s[i][j];
        while(i <= n && j <= n)
        {
            if(j == n)
            {
                ++i;
                str[tot++] = s[i][j];
            }
            else
            {
                ++j; 
                str[tot++] = s[i][j];
            }
            
            while(true)
            {
                ++i; --j;
                str[tot++] = s[i][j];
                if(j == 1 || i == n)break;
            }
            if(j == 1 && i != n)
            {
                ++i;
                str[tot++] = s[i][j];
            }
            else if(i == n)
            {
                ++j;
                str[tot++] = s[i][j];
            }
            while(true)
            {
                --i; ++j;
                str[tot++] = s[i][j];
                if(i == 1 || j == n)break;
            }
        }
        // for(int i = 1; i <= tot; ++i)cout << str[i];cout << endl;
        int l = 1, r = n, up = 1, dn = n;
        tot = 1;
        while(l <= r && up <= dn)
        {
            for(int i = l; i <= r; ++i)t[up][i] = str[tot++];
            ++up;
            for(int i = up; i <= dn; ++i)t[i][r] = str[tot++];
            --r;
            for(int i = r; i >= l; --i)t[dn][i] = str[tot++];
            --dn;
            for(int i = dn; i >= up; --i)t[i][l] = str[tot++];
            ++l;
        }
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
                cout << t[i][j];
            cout << endl;
        }
    }
    
    // cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
    return 0;
}

G - Liaoning Ship’s Voyage

啊,,,计算几何+bfs,,

判断一下每一个点之间合不合法,,连边bfs即可,,

判断就是看这两个点在不在三角形里,,三角形里的点一定是没有边的,有相交的也不行,,,但是因为边上点可以走,,所以要判断一下在边上的情况,,尤其是:

2017北京区域赛

这样的情况我以为中间判了,,但是实际没判,,,疯狂wa,,,自闭,,,

#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(TM(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e4 + 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;

// .......
int sgn(double x){
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}
struct Point{
    double x, y;
    Point(){}
    Point(double _x, double _y){
        x = _x; y = _y;
    }
    void input(){
        // scanf("%lf%lf", &x, &y);
        cin >> x >> y;
    }
    bool operator==(Point b)const{
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator <(Point b)const{
        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
    }
    Point operator-(const Point &b)const{
        return Point(x - b.x, y - b.y);
    }
    double operator*(const Point &b)const{
        return x * b.x + y * b.y;
    }
    double operator^(const Point &b)const{
        return x * b.y - y * b.x;
    }
    double distance(Point p){
        return hypot(x - p.x, y - p.y);
    }
}p1, p2, p3;
struct Line{
    Point s, e;
    Line(){}
    Line(Point _s, Point _e){
        s = _s;
        e = _e;
    }
    bool operator==(Line v){
        return (s == v.s) && (e == v.e);
    }
    void init(Point a, Point b){
        s = a;
        e = b;
    }
    double length(){
        return s.distance(e);
    }
    double dispointtoline(Point p){
        return fabs((p - s) ^ (e - s)) / length();
    }
    double dispointtoseg(Point p){
        if(sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
            return min(p.distance(s), p.distance(e));
        return dispointtoline(p);
    }
    int segcrosseg(Line v){
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        int d3 = sgn((v.e - v.s) ^ (s - v.s));
        int d4 = sgn((v.e - v.s) ^ (e - v.s));
        if((d1 ^ d2) == -2 && (d3 ^ d4) == -2)return 2;
        return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
            (d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
            (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
            (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
    }
    bool pointonseg(Point p){
        return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0;
    }
    double getarea(Point p){
        double area = dispointtoline(p) * length() / 2;
        return area;
    }
}l1, l2, l3;

// ........


struct egde{
    int to, nxt;
}edge[maxn << 1];
int tot, head[maxn << 1];
void init(){
    tot = 0;
    memset(head, -1, sizeof head);
}
void addedge(int u, int v){
    // if(!(tot & 1))cout << u << "->" << v << endl;
    edge[tot].to = v;
    edge[tot].nxt = head[u];
    head[u] = tot++;
}
int dis[maxn];
bool vis[maxn];
queue<int> q;
void dijkstra(int n, int s)
{
    memset(vis, false, sizeof vis);
    memset(dis, inf, sizeof dis);
    while(!q.empty())q.pop();
    q.push(s);
    dis[s] = 0;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        if(vis[u])continue;
        vis[u] = true;
        for(int i = head[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if(dis[v] > dis[u] + 1)
            {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }   
}

int n;
char mp[25][25];
map<Point, bool> mp1, mp2, mp3, p;
inline int getidx(int x, int y){return x * n + y;}
bool check(Point a, Point b)
{
    Line l = Line(a, b);
    // if(a.x == 0 && a.y == 1){
    //     cout << a.x << " " << a.y << "; " << b.x << " " << b.y << endl;
    //     cout << l.segcrosseg(l1) << endl;
    //     cout << l.segcrosseg(l2) << endl;
    //     cout << l.segcrosseg(l3) << endl;
    // }
    if(l.segcrosseg(l1) == 2 || l.segcrosseg(l2) == 2 || l.segcrosseg(l3) == 2)return false;
    if(mp1[a] && mp1[b])return true;
    else if(mp2[a] && mp2[b])return true;
    else if(mp3[a] && mp3[b])return true;
    if(!p[a] || !p[b])
    {
        if((mp1[a] && mp2[b]) || (mp1[a] && mp3[b]) || (mp2[a] && mp1[b]) || (mp2[a] && mp3[b]) || (mp3[a] && mp1[b]) || (mp3[a] && mp2[b]))return false;
    }
    if(l.segcrosseg(l1) == 1 && l.segcrosseg(l2) == 1 && l.segcrosseg(l3) == 1)return false;
    if(l.segcrosseg(l1) == 1 || l.segcrosseg(l2) == 1 || l.segcrosseg(l3) == 1)return true;
    
    // if(l.segcrosseg(l1) == 1 || l.segcrosseg(l2) == 1 || l.segcrosseg(l3) == 1)return false;
    return true;
}
int main()
{
    // double pp = clock();
    // freopen("233.in", "r", stdin);
    // freopen("233.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    while(cin >> n)
    {
        p1.input(); p2.input(); p3.input();
        for(int i = n - 1; i >= 0; --i)cin >> mp[i];
        mp[0][0] = '.';
        l1.init(p1, p2); l2.init(p1, p3); l3.init(p2, p3);
        double area = l1.getarea(p3);
        mp1.clear(); mp2.clear(); mp3.clear(); p.clear();
        p[p1] = true; p[p2] = true; p[p3] = true;
        for(int i = 0; i <= n - 1; ++i)
        {
            for(int j = 0; j <= n - 1; ++j)
            {
                if(mp[i][j] == '#')continue;
                Point p = Point(j, i);
                double area1 = l1.getarea(p);
                double area2 = l2.getarea(p);
                double area3 = l3.getarea(p);
                if(l1.pointonseg(p))mp1[p] = true;
                if(l2.pointonseg(p))mp2[p] = true;
                if(l3.pointonseg(p))mp3[p] = true;
                if(sgn(area1 + area2 + area3 - area) == 0)mp[i][j] = '#';
                if(mp1[p] || mp2[p] || mp3[p])mp[i][j] = '.';
            }
        }
        int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
        int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
        Point p, q;
        init();
        for(int i = 0; i <= n - 1; ++i)
        {
            for(int j = 0; j <= n - 1; ++j)
            {
                if(mp[i][j] == '#')continue;
                p = Point((double)j, (double)i);
                for(int k = 0; k <= 7; ++k)
                {
                    int x = j + dx[k];
                    int y = i + dy[k];
                    if(x < 0 || x >= n || y < 0 || y >= n)continue;
                    if(mp[y][x] == '#')continue;
                    q = Point((double)x, (double)y);
                    if(check(p, q))
                        addedge(getidx(j, i), getidx(x, y)), addedge(getidx(x, y), getidx(j, i));
                }
            }
        }
        dijkstra(n * n, 0);
        // for(int i = 0; i <= n * n; ++i)cout << i << ": " << dis[i] << endl;
        if(dis[getidx(n - 1, n - 1)] == inf)cout << -1 << endl;
        else cout << dis[getidx(n - 1, n - 1)] << endl;
    }

    return 0;
}

(end)

相关标签: 区域赛