Diposting di | Edited on

传送门

付队！

许老师！

B.Aesthetics in poetry (暴力模拟)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
map<int,int>mp;
int a[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    bool flag=false;
    for(int i=2;i<=(n);i++){
        if(n%i==0){
            mp.clear();
            for(int j=0;j<n;j++)mp[a[j]%i]++;
            if(mp.size()==i){
                bool ok=false;
                for(int j=0;j<i;j++){
                    if(mp[j]!=n/i){ok=true;break;}
                }
                if(!ok){
                    cout<<i<<endl;return 0;
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

D.Maximizing Advertising (离散化)

题意

在平面内有两种点，让你用两个不相交的矩形把平面覆盖，让一个平面的黑点+另一个平面内的百白点数目最多

思路

直接枚举两平面的相隔点就行，数据太大无法计数用离散化解决

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
#define bug cout<<"mx="<<mx<<endl;
vector<int>x1,x2,y1,y2;
vector<int>X;
int sum1,sum2;
int vis1x[maxn],vis1y[maxn],sum1x[maxn],sum1y[maxn];
int vis2y[maxn],vis2x[maxn],sum2x[maxn],sum2y[maxn];
void get(int id){
    sum1x[id]=vis1x[id];
    sum1y[id]=vis1y[id];
    sum2x[id]=vis2x[id];
    sum2y[id]=vis2y[id];
    if(id){
        sum1x[id]+=sum1x[id-1];sum1y[id]+=sum1y[id-1];
        sum2x[id]+=sum2x[id-1];sum2y[id]+=sum2y[id-1];
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;char ch;
        cin>>x>>y>>ch;
        if(ch=='b')x1.push_back(x),y1.push_back(y),sum1++;
        else x2.push_back(x),y2.push_back(y),sum2++;
        X.push_back(x);X.push_back(y);
    }
    sort(X.begin(),X.end());
    X.erase(unique(X.begin(),X.end()),X.end());
    int sz=X.size();
    for(int i=0;i<x1.size();i++){
        x1[i]=lower_bound(X.begin(),X.end(),x1[i])-X.begin();
        y1[i]=lower_bound(X.begin(),X.end(),y1[i])-X.begin();
    }
    for(int i=0;i<x2.size();i++){
        x2[i]=lower_bound(X.begin(),X.end(),x2[i])-X.begin();
        y2[i]=lower_bound(X.begin(),X.end(),y2[i])-X.begin();
    }
    int mx=0;
    for(int i=0;i<sum1;i++){
        vis1x[x1[i]]++;
        vis1y[y1[i]]++;
    }
    for(int i=0;i<sum2;i++){
        vis2x[x2[i]]++;
        vis2y[y2[i]]++;
    }
    for(int i=0;i<sz;i++){
       get(i);
        mx=max(mx,sum1x[i]+sum2-sum2x[i]);
        mx=max(mx,sum2x[i]+sum1-sum1x[i]);
        mx=max(mx,sum1y[i]+sum2-sum2y[i]);
        mx=max(mx,sum2y[i]+sum1-sum1y[i]);
    }
    cout<<mx<<endl;
    return 0;
}

E.Group work (组合数学)

题意

N个学生分组，可以大于等于三个人一组 问分组数量有多少中

思路

Cn0+Cn1+Cn2+Cn3+…+Cnn等于2^n 减去取0个和取1个就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
#define bug cout<<"mx="<<mx<<endl;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    cout<<((1LL<<n)-n-1)<<endl;
    return 0;
}

G.Running a penitentiary (区间交集)

题意

有n个警察，第i个警察看管监狱的区间是【Li，Ri】。
有两种操作：C i l r ：把第i个警察的区间变为【l，r】。
？l r ：询问从第l个警察到第r个警察共同看管的区间长度是多少

H. Wine Production (莫队算法+离散化)

题意

给出N个数，每次查询一个区间 返回一个K,表示区间有K个数出现了至少K个次

题解

首先用num[x]表示X出现了多少次，cnt[x]表示出现次数为X的个数，

因为N个数有负数所以需要离散化一下， 然后就是莫队算法瞎搞(模板是从1开始的，我一开始是从0开始的。。)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
#define bug cout<<"mx="<<mx<<endl;

// ---
// 莫队算法,可以解决一类静态,离线区间查询问题。分成 $\sqrt{x}$ 块,分块排序。
// ---
int unit;
int a[maxn];
vector<int> b;
struct query { int L, R, id; };
int ans[maxn];
int num[maxn];///出现次数
int cnt[maxn]; ///出现个数
int tmp;
void add(int x){
    num[x]++;cnt[num[x]]++;
    if(min(num[x],cnt[num[x]])>tmp)tmp=min(num[x],cnt[num[x]]);
}
void del(int x){
    cnt[num[x]]--;
    if(num[x]==tmp&&cnt[num[x]]<tmp){
        tmp=cnt[num[x]];
    }
    num[x]--;
}
void solve(query node[], int m)
{
    memset(ans, 0, sizeof(ans));
    sort(node, node + m, [](query a, query b) {
        return a.L / unit < b.L / unit
               || a.L / unit == b.L / unit && a.R < b.R;
    });
    int L = 0, R = -1;
    for (int i = 0; i < m; i++)
    {
        while (node[i].L < L) add(a[--L]);
        while (node[i].L > L) del(a[L++]);
        while (node[i].R < R) del(a[R--]);
        while (node[i].R > R) add(a[++R]);
        ans[node[i].id] = tmp;
    }
}
query my[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    unit=sqrt(n);
    for(int i=0;i<n;i++)cin>>a[i],b.push_back(a[i]);
    sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end());
    for(int i=0;i<n;i++)a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin();
    for(int i=0;i<m;i++){
        cin>>my[i].L>>my[i].R;my[i].id=i;
        my[i].L--;my[i].R--;
    }
    solve(my,m);
    for(int i=0;i<m;i++)cout<<ans[i]<<endl;
    return 0;
}

I.A story about tea ()

J.Meme Wars （模拟）

思路

就按照题意构造字符串，第一次交超内存了，于是就判断长度是否大于N在构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
#define bug cout<<"mx="<<mx<<endl;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string s="a";
    int n;cin>>n;
    for(char c='b';c<'z'&&s.size()<n;c++)s=s+c+s;cout<<s[n-1];
    return 0;
}

Diposting di | Edited on

传送门

付队博客

C.Coolest Ski Route (记忆化搜索)

题意

给出一个有向图,求出一个权值最长的链,

题解

暴力dfs会超时,所以直接储存每个起点能走到的最远距离

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;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m;
struct node{
    int v,c;
};
vector<node>G[maxn];
int dp[maxn];
int dfs(int now){
    if(dp[now]!=-1)return dp[now];
    int ans=0;
    for(auto i:G[now]){
        ans=max(ans,dfs(i.v)+i.c);
    }
    return dp[now]=ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        G[x].push_back(node{y,z});
    }
    int mx=-inf;
    for(int i=1;i<=n;i++){
        if(dp[i]==-1){
            mx=max(mx,dfs(i));
        }
    }
    cout<<mx<<endl;
    return 0;
}

D.Down the Pyramid (不等式)

题意

金字塔的每一层都比上一层多一个，并且上一层的值是下一层的两个相邻之和

给出第n层，让你求出第N+1层的值有多少种可能性（需要保证每一个数都大于等于0）

题解

比赛一直想不出，付队做的.想法是，

假设给出的值是a1,a2,a3,a4,

假设第一个位置（b1）是X,那么第二个位置(b2)的值就是a1-x,第三个位置的值就是a2-(a1-x);

可以发现都和第一个假设的位置的值x有关,所以我们只要保证这个过程每个位置的值都大于0就可以求出X的可能取值

a1-x>=0 a2-a1-x>=0 ->x<=a1 x<=a2-a1;

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=0;
    int mi=0,mx=a[1];
    for(int i=1;i<=n;i++){
        ans=a[i]-ans;
        if(i&1)mx=min(mx,ans);
        else mi=max(mi,-ans);
    }
    if(mx<mi)cout<<0<<endl;
    else cout<<mx-mi+1<<endl;
    return 0;
}

Expired License (线性筛)

题意

给定你两个最多带5位小数的double型a,b，让你用用一对素数x y表示他们的比值。

题解

先把double变成整数型;注意四舍五入;然后求一下gcd 判断化简后是否都是素数即可

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-7;
bool check[maxn];
int phi[maxn];
int prime[maxn];
int tot;
void phi_and_prime_table(int N){
    memset(check,false,sizeof(check));
    phi[1]=1;
    tot=0;
    for(int i=2;i<=N;i++){
        if(!check[i]){
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>N)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else{
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    int t;
    phi_and_prime_table(10000000+10);
    check[1]=true;
    cin>>t;
    while(t--){
        double a,b;
        cin>>a>>b;
        int C=(int)((a+eps)*100000),D=(int)((b+eps)*100000);
        int gc=__gcd(C,D);
        C/=gc;D/=gc;
        if(!check[C]&&!check[D])cout<<C<<" "<<D<<endl;
        else if(C==1&&D==1)cout<<"2 2"<<endl;
        else
            cout<<"impossible"<<endl;
    }
    return 0;
}

F.Fighting Monsters (打表找规律)

题意

给出N个怪兽，问是否选择两个怪兽根据题意战斗之后 活下来的那个怪剩下一滴血

题解

根据题意打表后发现选择的两个怪兽血量必须符合斐波那契数列的相邻两项值

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>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int m[maxn];
bool isok(int a,int b){
    int aa=a,bb=b;
    int i=1;
    while(aa>0&&bb>0){
        if(i&1)aa-=bb;
        else bb-=aa;
        i++;
    }
    if(aa==1||bb==1)cout<<"a="<<a<<" b="<<b<<endl;
    aa=a,bb=b;
    i=1;
    while(aa>0&&bb>0){
        if(i&1)bb-=aa;
        else aa-=bb;
        i++;
    }
    if(aa==1||bb==1)cout<<"a="<<a<<" b="<<b<<endl;
}
int F[maxn];
int num[maxn];
int id[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
   /* for(int i=1;i<=1000;i++){
        for(int j=i;j<=1000;j++){
            isok(i,j);
        }
    }*/
    F[1]=F[2]=1;
    for(int i=3;i<=31;i++){
        F[i]=F[i-1]+F[i-2];
       // cout<<F[i]<<endl;
    }
    int n;
    cin>>n;
    int flag=0,one;
    for(int i=1;i<=n;i++){
        cin>>m[i];
        if(!flag&&m[i]==1)flag=1,one=i;
        num[m[i]]++;
        id[m[i]]=i;
    }
    int f=0;
    if(num[1]>=2){
        cout<<one<<" "<<id[1]<<endl;
        return 0;
    }
    for(int i=2;i<=30;i++){
        if(num[F[i]]&&num[F[i+1]]){
            f=1;
            cout<<id[F[i]]<<" "<<id[F[i+1]]<<endl;
            break;
        }
    }
    if(!f)cout<<"impossible"<<endl;
    return 0;
}

H.Hyper Illuminati

题意

给定一个数N(<1e16)，问是否存在n和s，满足1^n+2^n+3^n+…s^n=N；输出n+1，s

题解

slove by 付队，

如果2<=n<=53，我们发现s不会太大，我们可以把所有的都求出来；如果n>53，则有s<=2，我们可以把s=2的值都求出来。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll ans=0,n;
    cin>>n;
    for(int i=2;i<=53;i++){
        ans=0;
        for(ll j=1;j<=n;j++){
            ll tmp=1;
            for(ll k=1;k<=i;k++){
                if(tmp>n/j){tmp=n+1;break;}
                tmp*=j;
            }
            if(tmp>n)break;
            ans+=tmp;
            if(ans==n)return cout<<i+1<<" "<<j<<endl,0;
            if(ans>n)break;
        }
    }
    ll tmp=1;
    for(ll j=1;j<=n;j++){
        tmp*=2LL;
        if(j>=2){
            if(tmp+1==n)return cout<<j+1<<" "<<2<<endl,0;
        }
        if(tmp+1>=n)break;
    }
    cout<<"impossible"<<endl;
    return 0;
}

I.It’s Time for a Montage (枚举暴力)

题意

就是两边按顺序打架，如果当前相等就比下一个 直到比出胜负，但是主角可以选择每回合所有怪增加1点攻击，如果最后没怪并且主角攻击大于等于另一个就赢 ，问主角最少需要等多少回合;

题意

因为攻击力最大值只有1000 所以直接枚举暴力就行

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int h[maxn];
int v[maxn];
int isok(int x,int n){
    for(int i=1;i<=n;i++){
        if(h[i]-v[i]+x==0)continue;
        else if(h[i]-v[i]+x>0)return true;
        else return false;
    }
    return true;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=1;i<=n;i++)cin>>v[i];
    int ans=0;
    for(int i=0;i<=1000;i++){
        if(isok(i,n)){
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

Logic Puzzle

题意

：给你一个大格子，然后在中心格子填黑点，每个格子中有显示以它为中心的3*3格子有多少个黑点，让你构造中心格子的黑点， （就是扫雷

题解

从左上开始枚举对应的雷都是固定的，所以直接扫过去判断是否可以扫完就行

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int dx[9]={0,0,0,1,-1,1,1,-1,-1};
int dy[9]={0,1,-1,0,0,1,-1,1,-1};
int a[150][150],vis[150][150];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)cin>>a[i][j];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(a[i][j]==1){
                vis[i+1][j+1]=1;
                for(int k=0;k<=8;k++){
                    if(i+1+dx[k]>=0&&i+1+dx[k]<=n+1&&j+1+dy[k]>=0&&j+1+dy[k]<=m+1)
                        a[i+1+dx[k]][j+1+dy[k]]--;
                }
            }
        }
    }
    for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++){
        if(a[i][j]){
            cout<<"impossible"<<endl;return 0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(vis[i][j])cout<<"X";
            else cout<<".";
        }
        cout<<endl;
    }
    return 0;
}

Diposting di | Edited on

传送门

付队！

许老师！

Hello SCPC 2018! (签到)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{
    int value,id;
}a[maxn];
int cmp(node a,node b){
    return a.value<b.value;
}
int f[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("hello.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        for(int i=1;i<=12;i++)cin>>a[i].value,a[i].id=i;
        sort(a+1,a+1+12,cmp);
        memset(f,0,sizeof(f));
        for(int i=1;i<=4;i++)f[a[i].id]=i;
        int flag=0;
        for(int i=1;i<=4;i++){
            if(f[i]!=i){
                flag=1;
            }
        }
        if(flag)cout<<"no"<<endl;
        else cout<<"yes"<<endl;
    }
    return 0;
}

Binary Hamming (签到)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char s[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("hamming.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n,a1=0,b1=0,a2=0,b2=0;
        cin>>n;
        cin>>s;
        for(int i=0;i<n;i++)if(s[i]=='1')a1++;else b1++;
        cin>>s;
        for(int i=0;i<n;i++)if(s[i]=='1')a2++;else b2++;
        cout<<min(a1,b2)+min(b1,a2)<<endl;
    }
    return 0;
}

Portals (模拟,分类讨论)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char s[maxn];
int dx[2]={1,-1};
int n;
int S,T;
int dfs(int x,int i){
    if(x==n+1)return 0;
    if(x==0)return 0;
    if(s[x]=='#')return 0;
    if(s[x]=='o')return 1;
    if(s[x]=='s'||s[x]=='e')return 1;
    return dfs(x+dx[i],i);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("portals.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<=n+10;i++)s[i]='#';
        cin>>s+1;
        int len=strlen(s+1);
        for(int i=1;i<=n;i++){
            if(s[i]=='s')S=i;
            if(s[i]=='e')T=i;
        }
        int neds=dfs(S+1,0)+dfs(S-1,1);
        int nedt=dfs(T+1,0)+dfs(T-1,1);
        int ans=1e9;
        if(s[S-1]=='o'||s[S+1]=='o'||s[S-1]=='e'||s[S+1]=='e')neds=1e9;
        if(s[T-1]=='o'||s[T+1]=='o'||s[T-1]=='s'||s[T+1]=='s')nedt=1e9;
        ans=min(neds,nedt);
        if(ans==1e9)cout<<-1<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

Carnival Slots （DP，记忆化搜索）

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char mp[550][550];

ll dp[505][505];
ll num[550];
ll value[550];
int r,c;

ll dfs(int x,int y){
    if(x==r+1){
        return value[y];
    }
    if(dp[x][y]!=-1)return dp[x][y];
    ll ans=0;
    ans=dfs(x+1,y);

    if(y-1>=1&&mp[x][y]!='.')ans=max(ans,dfs(x+1,y-1));
    if(y+1<=c&&mp[x][y]!='.')ans=max(ans,dfs(x+1,y+1));
    return dp[x][y]=ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("balls.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        cin>>r>>c;
        for(int i=1;i<=c;i++)cin>>num[i];
        for(int i=1;i<=r;i++){
            cin>>mp[i]+1;
        }
        for(int i=1;i<=c;i++)cin>>value[i];
        ll ans=0;
        memset(dp,-1,sizeof(dp));
        for(int i=1;i<=c;i++){
            ans+=dfs(1,i)*num[i]*1LL;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Bugged System (模拟)

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;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int x[maxn];
struct node{
    int s,d;
}my[maxn];
int in[maxn];
int out[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("bugged.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>x[i];
        ll ans=0;
        for(int i=1;i<=m;i++){
            cin>>my[i].s>>my[i].d;
            in[my[i].s]++;
            out[my[i].d]++;
            ans+=abs(x[my[i].s]-x[my[i].d]);
        }
        bool f=0;
        for(int i=1;i<=n;i++){
            if(in[i]!=out[i])f=1;
            in[i]=out[i]=0;
        }
        if(f)cout<<"-1"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

Tourists’ Tour (染色问题，拓扑)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>ve[maxn];
void add(int u,int v){
    ve[v].push_back(u);
    ve[u].push_back(v);
}
int color[maxn];
int vis[10];
int mx;
void dfs(int now){
   // cout<<"now="<<now<<endl;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<ve[now].size();i++){
        vis[color[ve[now][i]]]=1;
    }
    for(int i=1;i<10;i++){
        if(!vis[i]){
            color[now]=i;
            break;
        }
    }
    mx=max(mx,color[now]);
    for(int i=0;i<ve[now].size();i++)if(!color[ve[now][i]])dfs(ve[now][i]);
}
int a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("tour.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i],ve[i].clear();
		stack<int>pq;
		pq.push(1);
		for(int i=2;i<=n;i++){
            while(!pq.empty()&&a[pq.top()]<a[i])pq.pop();
            if(!pq.empty()){
                add(pq.top(),i);
            }
            pq.push(i);
		}
		stack<int>q;
		q.push(n);
		for(int i=n-1;i>=1;i--){
            while(!q.empty()&&a[q.top()]<a[i])q.pop();
            if(!q.empty()){
                add(q.top(),i);
            }
            q.push(i);
		}
		for(int i=1;i<=n;i++)reverse(ve[i].begin(),ve[i].end());
		for(int i=1;i<=n;i++)color[i]=0;
		mx=0;
		for(int i=1;i<=n;i++)if(color[i]==0)dfs(i);
		cout<<mx<<endl;
		for(int i=1;i<=n;i++)cout<<color[i]<<" ";
		cout<<endl;
    }
    return 0;
}

Is Topo Logical? (模拟)

Rise of the Robots (最小圆覆盖)

思路

首先感谢付队的模板！太快了

这题可以把题意转化成求点到所有直线距离的最短距离,然后为什么答案要取反呢，因为我们一开始是以原点为起点的

然后答案给出的是圆心为起点的，所以我们要把这个起点缩回原点。

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
#define mp make_pair
const double eps=1e-8;
const double pi=4*atan(1.0);
struct point{
    double x,y;
    point(double a=0,double b=0):x(a),y(b){}
};
int dcmp(double x){ return fabs(x)<eps?0:(x<0?-1:1);}
point operator +(point A,point B) { return point(A.x+B.x,A.y+B.y);}
point operator -(point A,point B) { return point(A.x-B.x,A.y-B.y);}
point operator *(point A,double p){ return point(A.x*p,A.y*p);}
point operator /(point A,double p){ return point(A.x/p,A.y/p);}
point rotate(point A,double rad){
    return point(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
bool operator ==(const point& a,const point& b) {
     return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double dot(point A,point B){ return A.x*B.x+A.y*B.y;}
double det(point A,point B){ return A.x*B.y-A.y*B.x;}
double dot(point O,point A,point B){ return dot(A-O,B-O);}
double det(point O,point A,point B){ return det(A-O,B-O);}
double length(point A){ return sqrt(dot(A,A));}
double angle(point A,point B){ return acos(dot(A,B)/length(A)/length(B));}
double distoline(point P,point A,point B)
{
    //点到直线距离
    point v1=B-A,v2=P-A;
    return fabs(det(v1,v2)/length(v1));
}
double distoseg(point P,point A,point B)
{
    //点到线段距离
    if(A==B) return length(P-A);
    point v1=B-A,v2=P-A,v3=P-B;
    if(dcmp(dot(v1,v2))<0) return length(v2);
    else if(dcmp(dot(v1,v3))>0) return length(v3);
    return fabs(det(v1,v2)/length(v1));
}
double Ployarea(vector<point>p)
{
    //多边形面积
    double ans=0; int sz=p.size();
    for(int i=1;i<sz-1;i++) ans+=det(p[i]-p[0],p[i+1]-p[0]);
    return ans/2.0;
}
bool SegmentProperIntersection(point a1,point a2,point b1,point b2)   {
    //规范相交
    double c1=det(a2-a1,b1-a1),c2=det(a2-a1,b2-a1);
    double c3=det(b2-b1,a1-b1),c4=det(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool isPointOnSegment(point p,point a1,point a2)
{
    //点是否在线段上
    return dcmp(det(a1-p,a2-p)==0&&dcmp(dot(a1-p,a2-p))<0);
}
int isPointInPolygon(point p,vector<point>poly)
{
    //判断点与多边形的位置关系
    int wn=0,sz=poly.size();
    for(int i=0;i<sz;i++){
        //在边上
        if(isPointOnSegment(p,poly[i],poly[(i+1)%sz])) return -1;
        int k=dcmp(det(poly[(i+1)%sz]-poly[i],p-poly[i]));
        int d1=dcmp(poly[i].y-p.y); int d2=dcmp(poly[(i+1)%sz].y-p.y);
        if(k>0&&d1<=0&&d2>0) wn++;
        if(k<0&&d2<=0&&d1>0) wn--;
    }
    if(wn!=0) return 1;//内部
    return 0;          //外部
}
double seg(point O,point A,point B){
    if(dcmp(B.x-A.x)==0) return (O.y-A.y)/(B.y-A.y);
    return (O.x-A.x)/(B.x-A.x);
}
pair<double,int>s[110*60];
double polyunion(vector<point>*p,int N){ //有多个才加*,单个不加，有改变的加&
    //求多边形面积并
    double res=0;
    for(int i=0;i<N;i++){
        int sz=p[i].size();
        for(int j=0;j<sz;j++){
            int m=0;
            s[++m]=mp(0,0);
            s[++m]=mp(1,0);
            point a=p[i][j],b=p[i][(j+1)%sz];
            for(int k=0;k<N;k++){
                if(i!=k){
                    int sz2=p[k].size();
                    for(int ii=0;ii<sz2;ii++){
                        point c=p[k][ii],d=p[k][(ii+1)%sz2];
                        int c1=dcmp(det(b-a,c-a));
                        int c2=dcmp(det(b-a,d-a));
                        if(c1==0&&c2==0){
                            if(dcmp(dot(b-a,d-c))){
                                s[++m]=mp(seg(c,a,b),1);
                                s[++m]=mp(seg(c,a,b),-1);
                            }
                        }
                        else{
                            double s1=det(d-c,a-c);
                            double s2=det(d-c,b-c);
                            if(c1>=0&&c2<0) s[++m]=mp(s1/(s1-s2),1);
                            else if(c1<0&&c2>=0) s[++m]=mp(s1/(s1-s2),-1);
                        }
                    }
                }
            }
            sort(s+1,s+m+1);
            double pre=min(max(s[1].first,0.0),1.0),now,sum=0;
            int cov=s[0].second;
            for(int j=2;j<=m;j++){
                now=min(max(s[j].first,0.0),1.0);
                if(!cov) sum+=now-pre;
                cov+=s[j].second;
                pre=now;
            }
            res+=det(a,b)*sum;
        }
    }
    return -(res/2);
}
point jiaopoint(point p,point v,point q,point w)
{   //p+tv q+tw，点加向量表示直线，求直线交点
    point u=p-q;
    double t=det(w,u)/det(v,w);
    return p+v*t;
}
point GetCirPoint(point a,point b,point c)
{
    point p=(a+b)/2;    //ad中点
    point q=(a+c)/2;    //ac中点
    point v=rotate(b-a,pi/2.0),w=rotate(c-a,pi/2.0);   //中垂线的方向向量
    if (dcmp(length(det(v,w)))==0)    //平行
    {
        if(dcmp(length(a-b)+length(b-c)-length(a-c))==0) return (a+c)/2;
        if(dcmp(length(b-a)+length(a-c)-length(b-c))==0) return (b+c)/2;
        if(dcmp(length(a-c)+length(c-b)-length(a-b))==0) return (a+b)/2;
    }
    return jiaopoint(p,v,q,w);
}
point MinCircular(point *P,int n)
{
    //最小圆覆盖 ,看起来是O(N^3)，期望复杂度为O(N)
    random_shuffle(P+1,P+n+1);    //随机化
    point c=P[1]; double r=0;   //c 圆心,,//r 半径
    for (int i=2;i<=n;i++)
        if (dcmp(length(c-P[i])-r)>0)    //不在圆内
        {
            c=P[i],r=0;
            for (int j=1;j<i;j++)
                if (dcmp(length(c-P[j])-r)>0)
                {
                    c=(P[i]+P[j])/2.0;
                    r=length(c-P[i]);
                    for (int k=1;k<j;k++)
                        if (dcmp(length(c-P[k])-r)>0)
                        {
                            c=GetCirPoint(P[i],P[j],P[k]);
                            r=length(c-P[i]);
                        }
                }
        }
    //cout<<r<<":"<<c.x<<" "<<c.y<<endl;
    return c;
}
const int maxn=400010;
bool cmp(point a,point b){ return a.x==b.x?a.y<b.y:a.x<b.x; }
point f[maxn],c[maxn],ch[maxn];
void convexhull(point *a,int n,int &top)
{
    //水平序的Andrew算法求凸包。
    sort(a+1,a+n+1,cmp); top=0;
    for(int i=1;i<=n;i++){ //求下凸包
        while(top>=2&&det(ch[top-1],ch[top],a[i])<=0) top--;
        ch[++top]=a[i];
    }
    int ttop=top;
    for(int i=n-1;i>=1;i--){ //求上凸包
        while(top>ttop&&det(ch[top-1],ch[top],a[i])<=0) top--;
        ch[++top]=a[i];
    }
}
void P(double x)
{
    //if(fabs(x)<0.000001) puts("0.00000000"); else
    printf("%.9lf",x);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("robots.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n,R,r;
        cin>>n>>R>>r;
        int tot=1;
        f[tot].x=0;f[tot].y=0;
        for(int i=1;i<=n;i++){
            int a,b;cin>>a>>b;
            tot++;
            f[tot].x=f[tot-1].x+a;
            f[tot].y=f[tot-1].y+b;
        }
        point anw=MinCircular(f,tot);
        cout<<fixed<<setprecision(9);
        cout<<-anw.x<<" "<<-anw.y<<endl;
    }
    return 0;
}

Diposting di | Edited on

传送门

付队！

许老师！

B.Buildings （polya定理）

题意

B：给你m面墙，每面墙是n*n的格子，你有c种颜色，问你有多少种涂色方案。用polya定理

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
///a<mod 并且 p为素数
ll pow_mod(ll x, ll n, ll mod){
    ll res=1;
    while(n){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll inv(ll a,ll p){return pow_mod(a,p-2,p);}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m,c;
    cin>>n>>m>>c;
    ll ans=0;
    for(int i=0;i<m;i++){
        ans+=pow_mod(c,n*n*__gcd(i,m),mod);
        ans%=mod;
    }
    cout<<ans*inv(m,mod)%mod<<endl;
    return 0;
}

C.Joyride （分层图最短路）

题意

C：游乐场有n个设施，有m条人行道，游乐设施会花费ti的时间和pi的钱，人行道需要花费t的时间，你需要用最少的钱恰好游玩x的时间，起点是1，终点是1，求最少的钱是多少4

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const int inf=1e9+7;
int x,n,m,t;
vector<int>ve[maxn];
struct need{
  int t,p;
}ned[maxn];
struct node{
    int in;
    int w;
    int time;
};
int dis[maxn][maxn];
void dij(){
    queue<node>q;
    q.push(node{1,ned[1].p,ned[1].t});
    for(int i=0;i<=1000;i++){
        for(int j=0;j<=1000;j++)dis[i][j]=inf;
    }
    dis[1][ned[1].t]=ned[1].p;
    while(!q.empty()){
        node now=q.front();
        q.pop();
        int in=now.in,w=now.w,time=now.time;
        if(time+ned[in].t<=x&&w+ned[in].p<dis[in][time+ned[in].t]){
            dis[in][time+ned[in].t]=w+ned[in].p;
            q.push(node{in,dis[in][time+ned[in].t],time+ned[in].t});
        }
        for(int i=0;i<ve[in].size();i++){
            int nex=ve[in][i];
            int nextime=time+t+ned[nex].t;
            if(nextime<=x&&dis[nex][nextime]>w+ned[nex].p){
                dis[nex][nextime]=w+ned[nex].p;
                q.push(node{nex,w+ned[nex].p,nextime});
            }
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>x>>n>>m>>t;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        ve[a].push_back(b);
        ve[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        cin>>ned[i].t>>ned[i].p;
    }
    dij();
    if(dis[1][x]==inf)cout<<"It is a trap."<<endl;
    else cout<<dis[1][x]<<endl;
    return 0;
}

D.Pants On Fire (map+dfs,or 传递闭包)

题意

D 有n个已知串，给m个串，让你去判断他们是对的还是错的还是未知的

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const int inf=1e9+7;
map<string,int>mp;
int cnt;
bool ok[500][500];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string a,b,c,d,e;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a>>b>>c>>d>>e;
        if(!mp[a])mp[a]=++cnt;
        if(!mp[e])mp[e]=++cnt;
        ok[mp[a]][mp[e]]=true;
    }
    for(int k=1;k<=cnt;k++){
        for(int i=1;i<=cnt;i++){
            for(int j=1;j<=cnt;j++){
                ok[i][j]|=ok[i][k]&&ok[k][j];
            }
        }
    }
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c>>d>>e;
        if(!mp[a]||!mp[e]){cout<<"Pants on Fire"<<endl;continue;}
        int u=mp[a],v=mp[e];
        if(ok[u][v])cout<<"Fact"<<endl;
        else if(ok[v][u])cout<<"Alternative Fact"<<endl;
        else{
            cout<<"Pants on Fire"<<endl;
        }
    }
    return 0;
}
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const int inf=1e9+7;
map<string,int>mp;
int cnt;
vector<int>G[maxn];
bool dfs(int u,int v){

    for(int i=0;i<G[u].size();i++){
        if(G[u][i]==v)return true;
        bool ok=dfs(G[u][i],v);
        if(ok)return true;
    }
    return false;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string a,b,c,d,e;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a>>b>>c>>d>>e;
        if(!mp[a])mp[a]=++cnt;
        if(!mp[e])mp[e]=++cnt;
        G[mp[a]].push_back(mp[e]);
    }
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c>>d>>e;
        if(!mp[a]||!mp[e]){cout<<"Pants on Fire"<<endl;continue;}
        int u=mp[a],v=mp[e];
        if(dfs(u,v))cout<<"Fact"<<endl;
        else if(dfs(v,u))cout<<"Alternative Fact"<<endl;
        else{
            cout<<"Pants on Fire"<<endl;
        }
    }
    return 0;
}

F.Plug It In (匈牙利算法/二分图匹配/网络流)

题意

m个插口，n个电器 k个可以匹配的连接 ,问你最大匹配数，但是你有一次机会把一个接口变成三个一样的

思路

考虑暴力每次暴力把一个其中一个接口数+2跑匈牙利算法，复杂度N^3，然后发现其实第一次跑的最初的图是可以一直重复利用的，然后就直接把后面的多出来的接口拿去跑增广路就行。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
/// 二分图最大基数匹配

int mp[1550][1550];
int link[1550];
int n,m,k;
bool vis[1550];
int remain[1550];
bool match(int u){
    for(int i=1;i<=m;i++){
        if(vis[i]==0&&mp[u][i]){
            vis[i]=1;
            if(link[i]==-1||match(link[i])){
                link[i]=u;
                return 1;
            }
        }
    }
    return 0;
}


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int k;
    cin>>n>>m>>k;
    memset(link,-1,sizeof(link));
    for(int i=1;i<=k;i++){
        int a,b;
        cin>>a>>b;
        mp[a][b]=1;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(match(i))ans++;
    }
    for(int i=1;i<=m;i++){
        remain[i]=link[i];
    }
    int mx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)mp[n+1][j]=mp[n+2][j]=mp[i][j];
        for(int i=1;i<=m;i++){
            link[i]=remain[i];
        }
        int now=0;
        memset(vis,0,sizeof(vis));
        for(int j=n+1;j<=n+2;j++){
            if(match(j))now++;
        }
        mx=max(now,mx);
    }
    cout<<ans+mx<<endl;
    return 0;
}

G.Water Testing (皮克定理)

题意

给你一个多边形问你多边形中的整点个数有多少

思路

皮克定理

皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为2S=2a+b-2，其中a表示多边形内部的点数，b表示多边形边界上的点数，S表示多边形的面积。

其中，面积用每两条线的叉积计算

image

当O点为原点时，根据向量的叉积计算公式，各个三角形的面积计算如下：

S_OAB = 0.5(A_xB_y - A_y*B_x) 【(A_x，A_y)为A点的坐标】

S_OBC = 0.5(B_xC_y - B_y*C_x)

S_OCD = 0.5(C_xD_y - C_y*D_x)

S_ODE = 0.5(D_xE_y - D_y*E_x)

S_OEA = 0.5(E_xA_y - E_y*A_x)

边界的点数用gcd(a.x-b.x,a.y-b.y)计算

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Point{
    ll x,y;
}my[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>my[i].x>>my[i].y;
    }
    ll s=0,b=0;
    for(int i=0;i<n;i++){
        s+=my[i].x*my[(i+1)%n].y-my[(i+1)%n].x*my[i].y;
        b+=__gcd(abs(my[i].x-my[(i+1)%n].x),abs(my[i].y-my[(i+1)%n].y));
    }

    s/=2;
    s=abs(s);
    cout<<s-b/2+1<<endl;
    return 0;
}

I.Uberwatch (基础DP)

思路

对于每个点考虑两种情况，如果他不放必杀技那

如果他放必杀技，那么他就只能在i-m时间之前放的最大值加起来

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int a[maxn];
int dp[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int sum=0;
    for(int i=m+1;i<=n;i++){
        dp[i]=max(dp[i-1],dp[i-m]+a[i]);
    }
    cout<<dp[n]<<endl;
    return 0;
}

K.You Are Fired (签到)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{
    ll money;
    string name;

}my[maxn];
bool vis[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll n,d,k;
    cin>>n>>d>>k;
    for(int i=1;i<=n;i++){
        cin>>my[i].name>>my[i].money;
    }
    sort(my+1,my+1+n,[](node a,node b){
        return a.money>b.money;
    });
    ll ans=0,num=0;
    for(int i=1;i<=k;i++){
        ans+=my[i].money;
        vis[i]=true;
        num++;
        if(ans>=d)break;
    }
    if(ans<d)cout<<"impossible"<<endl;
    else{
        cout<<num<<endl;
        for(int i=1;i<=n;i++){
            if(vis[i])
            cout<<my[i].name<<", YOU ARE FIRED!"<<endl;
        }
    }
    return 0;
}

Diposting di | Edited on

传送门

付队！

C - Greetings! （状态压缩）

题意

给N种信件，你可以任意选择K种信封装信件，问你最少的浪费是多少

不能大的信件装进小信封中

思路

首先如果可以选择的信封数量比N大 那么每一种信件用一个特定的信封肯定不会有浪费

因为数据很小我们考虑状态压缩考虑哪些信件用同一种信封 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const int maxn=(1<<16)+50;
const int inf=1e8;
ll c[maxn];
struct node{
    ll w,h,t;
}my[20];
ll dp[20][maxn];

int main()
{
    int n,k;
    cin>>n>>k;
    memset(dp,127,sizeof(dp));
    for(int i=0;i<n;i++)cin>>my[i].w>>my[i].h>>my[i].t;
    for(int i=0;i<(1<<n);i++){
        ll ww=0,hh=0,sum=0,cnt=0;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                sum+=my[j].w*my[j].h*my[j].t;
                ww=max(ww,my[j].w);
                hh=max(hh,my[j].h);
                cnt+=my[j].t;
            }
        }
        dp[1][i]=c[i]=(ww*hh*cnt-sum);
    }
    for(int i=2;i<=k;i++){
        dp[i][0]=0;
        for(int sta=0;sta<(1<<n);sta++){
            for(int t=sta;t;t=(t-1)&sta){
                dp[i][sta]=min(dp[i][sta],dp[i-1][t]+c[sta^t]);
            }
        }
    }
    cout<<dp[k][(1<<n)-1];

    return 0;
}

F - Mountain Scenes (DP)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const int maxn=5e5+50;
const int inf=1e8;
ll dp[150][25000];

int main()
{
   int n,w,h;
   cin>>n>>w>>h;
   dp[0][0]=1;
   for(int i=1;i<=w;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=h;k++){
                dp[i][j+k]+=dp[i-1][j];
                dp[i][j+k]%=mod;
            }
        }
    }
    ll ans=0;
    for(int i=0;i<=n;i++){
        ans+=dp[w][i];
        ans%=mod;
    }
    if(w*h<=n)ans=(ans-h+mod-1)%mod;
    else ans=(ans-n/w+mod-1)%mod;
    cout<<ans<<endl;
    return 0;
}

I - Tourists (LCA)

思路

很像wls面试我时出的题目

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const int maxn=2e5+50;
const int inf=1e8;

int Next[maxn<<1],To[maxn<<1],Laxt[maxn<<1];
int cnt;
void add(int u,int v){
    Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;
}

int n;
int fa[maxn][50],dep[maxn];
void dfs(int u,int faa){
    fa[u][0]=faa;
    dep[u]=dep[faa]+1;
    for(int i=Laxt[u];i;i=Next[i]){
        if(To[i]==faa)continue;
        dfs(To[i],u);
    }
}
void init(){
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            int f=fa[j][i-1];
            fa[j][i]=fa[f][i-1];
        }
    }
}
int lca(int p,int q){
    if(dep[p]<dep[q])swap(p,q);
    for(int i=20;i>=0;i--){
        if(dep[fa[p][i]]>=dep[q])p=fa[p][i];
    }
    if(p==q)return q;
    for(int i=20;i>=0;i--){
        if(fa[p][i]!=fa[q][i]){
            p=fa[p][i];q=fa[q][i];
        }
    }
    return fa[p][0];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    ll ans=0;
    init();
    for(int i=1;i<=n;i++){
        for(int j=2*i;j<=n;j+=i){
            int f=lca(i,j);
            ans+=dep[i]+dep[j]-2*dep[f]+1;
        }
    }
    printf("%lld\n",ans);
    return 0;
}