B

lyf

C

wd

A

zrc

模拟

J

zrc

题意：给定一个$n*n(n\le 1000)$的国际象棋棋盘，上面有$m\le 1000$个rook(城堡)(中国象棋的车)，现在每一步进行一个操作，即选择其中一个rook把能吃到的另一个rook吃掉，直到进行不了这样的操作(每一步都必须吃，不能进行普通移动)。问到结束的时候最多吃了几个rook，最少吃了几个。

解：

先考虑最多吃了几个。显然如果对每一对同一行的和每一对同一列rooks连边，所得连通块大小-1即这个连通块可以最多吃掉的rook数量。这个步骤在模拟赛时我用了并查集做，把每一行和每一列都开成一个size是0的点。复杂度$O((m+2n)\cdot\alpha(m+2n))$,但题解说深搜可以复杂度$O(m)$.不是很懂应该怎么操作。

再考虑最少吃了几个。模拟赛时lyf提供了一个几乎正确的贪心算法，即每次把入度最大的点删去，但对于3*3，9个rooks全满的情况就不行。思考许久，发现好像其实这玩意是个二分图上最小割。先把列和行都看成点，把S对列点连边，T对行点连边，每存在一个rook都增加一条相应的列点和边点之间的边。显然每行及每列最终最多只能存在一个rook，感受一下(实际上是不会说明怎么证)就可以发现这个显然是对的，样例也都对。由于数据范围极小，简短的匈牙利算法即可解决。

D

wd

E

lyf

题意：给定$n\le10^5$种货物,$m\le10^5$种交换条件，每种条件指的是1个a可以换x个b。假设货物都是无限的，问是否存在换来换去导致一个人可以无限获利的情况。

解：

显然建图，刚开始的想法是建一个DAG，从a到b连一条x的边，转化为求DAG上是否存在两条路径使得路径起点终点都相同但路径的乘积不同。这种想法一直没有结果，但DAG太诱人很难令人放弃。但其实最后还是换了个思路，不需要建DAG。对于刚才所说的DAG，每条边都加上一条权值1/x的反向边，并直接搜索(BFS DFS皆可)就做完了。题解说double的精度是够用的，但我们当时取了模数。当模数取1e9+7时是错误的，取998244353以及1e9+9也是错误的，取其中任意两个双哈希也是错误的。但是模拟赛时尝试用1e9+7和19260817就过了。赛后发现19260817单哈希就能过。+1s

复杂度$O(m)$

题解上说数据就是对着那几个有名的质数卡的。如果说是cf赛制的话，的确是要很小心别人用构造数据hack或者因此fst。但如果真的icpc赛制这么搞未免有点恶心。

G

wd

题意：给定一个矩阵，每个位置上有1~9的数字和+*两种符号，从左上角出发每一步只能向右或者向下走到达右下角，保证每条这样的路径组成的算式合法，问每个这样算式的和是多少。

解：

DP，开三个DP数组

补题

K

题意：有一架轰炸机，每到一个点就会以当前所在点为左上角把给定01矩阵中1的位置轰炸一次。轰炸机按照给定的上下左右顺序移动，问最终被轰炸了K次及以上的点有几个，题目保证不会炸到边界外

解：

首先可以把移动的过程模拟出来得到以每个点为左上角轰炸了几次。那么接下来要做的就是对一个01矩阵和一个记着次数的矩阵进行某种操作得到结果。可以发现这个过程非常像多项式相乘，考虑FFT。首先把二维情况压扁到一维然后思考一下发现直接FFT就做完了…裸的不行

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//by Richard
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
const int inf=0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> pairs;
///////////////////////read5.1///////////////////////
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
////////////////variables&functions//////////////////
const int maxn=2097153;
const double pi=3.1415926535897932384626433832795028841971693993751058209749446;
int r[maxn];
struct cp
{
    double x,y;
    cp(double xx=0,double yy=0):x(xx),y(yy){}
    cp operator+(const cp &b){return cp(x+b.x,y+b.y);}
    cp operator*(const cp &b){return cp(x*b.x-y*b.y,x*b.y+y*b.x);}
    cp operator-(const cp &b){return cp(x-b.x,y-b.y);}
    cp operator/(const int &b){return cp(x/b,y/b);}
}a[maxn],b[maxn];
void swap(cp &a,cp &b){cp temp=a;a=b;b=temp;}
void FFT(cp *a,int n,int op)
{
    rep(i,0,n-1) if (i<r[i]) swap(a[i],a[r[i]]);
    for (int i=1;i<n;i<<=1)
    {
        cp wn(cos(pi/i),op*sin(pi/i));
        for (int j=0;j<n;j+=i<<1)
        {
            cp w(1,0);
            for (int k=0;k<i;k++,w=w*wn)
            {
                cp x=a[j+k],y=a[i+j+k]*w;
                a[j+k]=x+y;
                a[i+j+k]=x-y;
            }
        }
    }
}
void solve(int n,int m)
{
    int l=0;
    for (m+=n-2,n=1;n<=m;n<<=1,l++);
    rep(i,0,n-1) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    FFT(a,n,1);FFT(b,n,1);
    rep(i,0,n-1) a[i]=a[i]*b[i];
    FFT(a,n,-1);
    rep(i,0,n-1) a[i]=a[i]/n;
}
char s[maxn];
int main()
{
    int n,m,k,l;
    read(n,m);read(k,l);
    rep(i,0,n-1)
        rep(j,0,n-1) 
        {
            char ch=getchar();
            while (ch=='\n'||ch==' ') ch=getchar();
            if (ch=='X') b[i*m+j].x=1;
        }
    scanf("%s",s);
    int nowx=0,nowy=0;
    rep(i,0,l-1) 
    {
        if (s[i]=='U') nowy--;
        else if (s[i]=='L') nowx--;
        else if (s[i]=='D') nowy++;
        else if (s[i]=='R') nowx++;
        a[nowy*m+nowx].x++;
    }
    solve(m*m,m*m);
    // rep(i,0,(m)*(m)-1) printf("%lld%c",(LL)(a[i].x+0.5),(i+1)%m?' ':'\n');
    int ans=0;
    rep(i,0,m*m-1) if ((LL)(a[i].x+0.5)>=k) ans++;
    cout<<ans<<endl;
    return 0;
}

F

题意：给定200个-1000到1000的点，求平面上点与前k远的给定点距离之和的最小值

解：

模拟赛时没有想法，估计得有几十万个峰，模拟退火也很难跑出来。

有想过尝试打平面情况的表找找看有没有什么性质，但是没时间了

结束后发现，可以证明是单峰的，那么显然可以三分套三分解决

同时，由于是单峰，模拟退火基本退化为爬山，当然也能跑出来

ZRC三分套三分:

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//by Richard
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
const int inf=0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> pairs;
///////////////////////read5.1///////////////////////
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
////////////////variables&functions//////////////////
const int maxn=111111;
int n,k;
double x[maxn],y[maxn],dis[maxn];
inline double sqr(double x){return x*x;}
double calc(double xx,double yy)
{
    rep(i,1,n) dis[i]=sqrt(sqr(x[i]-xx)+sqr(y[i]-yy));
    sort(dis+1,dis+1+n);
    double ans=0;
    per(i,n,n-k+1) ans+=dis[i];
    return ans;
}
double solve(double x)
{
    double l=-1001,r=1001;
    while (r-l>1e-5)
    {
        double ll=2*l/3+r/3,rr=2*r/3+l/3;
        double ansll=calc(x,ll),ansrr=calc(x,rr);
        if (ansll<ansrr) r=rr;
        else l=ll;
    }
    return calc(x,(r+l)/2);
}
int main()
{
    read(n,k);
    rep(i,1,n) scanf("%lf%lf",x+i,y+i);
    double l=-1001,r=1001;
    while (r-l>1e-5)
    {
        double ll=2*l/3+r/3,rr=2*r/3+l/3;
        double ansll=solve(ll),ansrr=solve(rr);
        if (ansll<ansrr) r=rr;
        else l=ll;
    }
    printf("%.6lf\n",solve((l+r)/2));
    return 0;
}


LYF 模拟退火

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
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) x.begin(), x.end()
#define fi first
#define se second

using namespace std;
typedef long long ll;

const int N = 2e2 + 5;
const double radio = 0.997, eps = 1e-10;

int n, k, x[N], y[N];

double dis(double nx, double ny, int x, int y) {
    return sqrt((nx - x) * (nx - x) + (ny - y) * (ny - y));
}

double calc(double nx, double ny) {
    vector<double> vc;
    for (int i = 1; i <= n; i++) {
        vc.push_back(dis(nx, ny, x[i], y[i]));
    }
    sort(all(vc));
    double res = 0;
    for (int i = n - k; i < n; i++) res += vc[i];
    return res;
}

double curx, cury, ans;

double gen() {
    return (double) rand() / RAND_MAX * 2 - 1;
}

void simulated_annealing() {
    double t = 2000;
    while(t > eps) {
        double nx, ny, nans;
        nx = curx + gen() * t;
        ny = cury + gen() * t;
        nans = calc(nx, ny);
        double delta = nans - ans;
        if (exp(-delta * 100 / t) > gen()) curx = nx, cury = ny, ans = nans;
        t *= radio;
    }
}
int main() {
    cin >> n >> k;
    srand(time(NULL));
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &x[i], &y[i]);
    }
    double output = 99999999999;
    for (int i = 1; i <= 20; i++) {
        curx = rand() % 4000 - 2000;
        cury = rand() % 4000 - 2000;
        ans = calc(curx, cury);
        simulated_annealing();
        output = min(output, ans);
    }
    printf("%.4f", output);
    return 0;
}