E - Cats and Fish

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

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

#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '
'
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 '
'
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即可，，

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

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

#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '
'
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)