模板

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
#include<bits/stdc++.h>
using namespace std;

#define lld long long
#define lf double
#define endl '\n'
#define llu unsigned long long
#define ci const int
#define clld const long long
#define cllu const unsigned long long
#define mo (1e9+7)
#define pi (acos(-1))
#define gc() getchar()
#define repp(i,a,b) for(lld i=(a);i<=(b);i++)
#define repm(i,a,b) for(lld i=(a);i>=(b);i--)
#define ret return
#define ct continue
#define elif else if
#define pii pair<int,int>
#define mp make_pair
#define srepp(i,a) for(auto i=a.begin();i!=a.end();i++)
#define srepm(i,a) for(auto i=--a.end();i!=--a.begin();i--)
#define vi vector <int>
#define vii vector <pair<int,int>>
#define vlld vector <long long>
#define st struct
#define M 403
#define P

2025.1.25

马的遍历

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
int n,m,x,y,a[M][M];
vector<pii>d;
queue<pii>q;
bool vd(pii s)
{
    if(s.first<=0||s.second<=0||s.first>=n+1||s.second>=m+1)
    ret 1;
    ret 0;
}
void bfs()
{
    repp(i,1,n)
    repp(j,1,m)
    a[i][j]=-1;
    a[x][y]=0;
    q.push(mp(x,y));
    while(q.size())
    {
        pii now=q.front();q.pop();
        repp(i,0,7)
        {
            pii nx=mp(now.first-d[i].first,now.second-d[i].second);
            if(vd(nx))ct;
            if(a[nx.first][nx.second]==-1)
            {
                a[nx.first][nx.second]=a[now.first][now.second]+1;
                q.push(nx);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>x>>y;
    d.push_back(mp(-2,1));
    d.push_back(mp(-2,-1));
    d.push_back(mp(2,1));
    d.push_back(mp(2,-1));
    d.push_back(mp(1,2));
    d.push_back(mp(1,-2));
    d.push_back(mp(-1,2));
    d.push_back(mp(-1,-2));
    bfs();
    repp(i,1,n)
    {
        repp(j,1,m)
        {
            cout<<a[i][j]<<"    ";
        }
        cout<<endl;
    }
    ret 0;
}

luogu P2895

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
bool s[304][304] ,biao,vis[304][304],ditu[304][304];int maxt,mint,t;
queue<pii>q;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
unordered_map<int,vii>tu;//是unordered而不是multi
bool vd(int x,int y)
{
    if(ditu[x][y]||x<=0||y<=0)ret 0;
    ret 1;
}
void bfs()
{
   q.push(mp(1,1));
   while(q.size())
   {
    int cishu=q.size();
    if(tu.find(t)!=tu.end() )
    {
        for(auto it : tu[t])
        {
            int xx=it.first;int yy=it.second;
            ditu[xx][yy]=ditu[xx-1][yy]=ditu[xx][yy-1]=ditu[xx+1][yy]=ditu[xx][yy+1]=1;
        }
    }
    repp(i,1,cishu)
    {
        pii it=q.front();q.pop();
        int xx=it.first;int yy=it.second;
        if(vis[xx][yy]){
            mint=t;ret;
        }
        if(ditu[xx][yy])ct;
        ditu[xx][yy]=1;
            repp(i,0,3)
            {
                if(vd(xx-dx[i],yy-dy[i]))
                q.push(mp(xx-dx[i],yy-dy[i]));
            }
    }
    t++;
   }
}
int main()
{
    //ios::sync_with_stdio(0);cin.tie(0);
    int m;mint = 1002;
    cin>>m;
    repp(i,1,m)
    {
        int x,y,t;
        cin>>x>>y>>t;
        x++;y++;
        tu[t].push_back(mp(x,y));
        s[x][y]=s[x-1][y]=s[x+1][y]=s[x][y-1]=s[x][y+1]=1;
    }
    repp(i,1,302)
    repp(j,1,302)
    {
        if(s[i][j]==0)
        {
            biao=1;
            vis[i][j]=1;
        }
    }
    if(!biao)
    {
        cout<<-1;
    }
    else{
        bfs();
    }
    if(mint==1002)
    {
        cout<<-1;
    }
    else
    {
        cout<<mint;
    }
    ret 0;
}

2025.2.4

P1955 程序自动分析

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
int f[200003],cnt;bool biao;
int get(int x)
{
    if(x==f[x])ret x;
    ret (f[x]=get(f[x]));
}
void merge(int x,int y)
{
     (f[get(x)]=get(y)) ;
}
int main()
{
    //ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;
    while(t--)
    {
        int n,e,x,y;
        cin>>n ;
        biao=cnt=0;
    memset(f,0,sizeof(f));
    unordered_map<int,int>p;
    vii ck ;
    repp(i,1,2*n+1)
    {
        f[i]=i;
    }
    repp(i,1,n)
    {
        cin>>x>>y>>e;
        if(p.find(x)!=p.end())x=p[x];
        else    {p[x]=++cnt;x=cnt;}
        if(p.find(y)!=p.end())y=p[y];
        else    {p[y]=++cnt;y=cnt;}
        if(e)
        merge(x,y);
        else
        ck.push_back(mp(x,y));
    }
    for(auto it:ck)
    {
        if(get(it.first)==get(it.second)){
            biao=1;
            break;
        }
    }
    if(biao)cout<<"NO";
    else    cout<<"YES";
    cout<<endl;
    }
    ret 0;
}

P1090 合并果子

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
lld heap[M],Size,n;
void Up(lld x)
{
    while(x>1)
    {
        if(heap[x]<heap[x/2])
        {swap(heap[x],heap[x/2]);
        x/=2;}
    else break;
    }
}
void Down(lld x)
{
    lld s=x*2;
    while(s<=Size)
    {
        if(s<Size&&heap[s]>heap[s+1])s++;
        if(heap[s]<heap[x])
        {
            swap(heap[s],heap[x]);
            x=s;s=x*2;
        }
        else break;

    }
}
void Insert(lld x)
{
    heap[++Size]=x;
    Up(Size);
}
lld Top()
{
    ret heap[1];
}
void Pop()
{
    heap[1]=heap[Size--];
    Down(1);
}
int main()
{
    //ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    repp(i,1,n)
    {
        lld op;
        cin>>op;
        Insert(op);
    }
    if(n==1)
    {
        cout<<heap[1];
        ret 0;
    }
    lld sum=0;
    repp(i,1,n-1)
    {
        lld tem=Top();
        Pop();
        tem+=Top();
        Pop();
        sum+=tem;
        Insert(tem);
    }
    cout<<sum;
    ret 0;
}

25.2.7

P1111 修复公路

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;

#define lld long long
#define lf double
#define endl '\n'
#define llu unsigned long long
#define ci const int
#define clld const long long
#define cllu const unsigned long long
#define mo (1e9+7)
#define pi (acos(-1))
#define gc() getchar()
#define repp(i,a,b) for(lld i=(a);i<=(b);i++)
#define repm(i,a,b) for(lld i=(a);i>=(b);i--)
#define ret return
#define ct continue
#define elif else if
#define pii pair<int,int>
#define mp make_pair
#define srepp(i,a) for(auto i=a.begin();i!=a.end();i++)
#define srepm(i,a) for(auto i=--a.end();i!=--a.begin();i--)
#define vi vector <int>
#define vii vector <pair<int,int>>
#define vlld vector <long long>
#define st struct
#define M 1003
#define P
int n,m,fa[M],cnt,maxt;
vector<pair<int,pair<int,int>>>a;
int get(int i)
{
    if(i==fa[i])ret i;
    ret(fa[i]=get(fa[i]));
}
void merge(int i,int j)
{
    fa[get(i)]=get(j);//别忘了是要根与根合并,一个get()都不能少
}
int main()
{
    //ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    repp(i,1,n)
    fa[i]=i;
    a.push_back(mp(0,mp(0,0)));
    repp(i,1,m)
    {
        int x,y,t;
        cin>>x>>y>>t;
        a.push_back(mp(t,mp(x,y)));
    }
    sort(a.begin()+1,a.end());//按时间来排序处理就好
    repp(i,1,m)
    {
        int t=a[i].first;
        int x=(a[i].second).first;
        int y=(a[i].second).second;
        if(get(x)!=get(y))
        {
            cnt++;
            merge(x,y);
        }
        if(cnt==n-1)
        {
            cout<<t;
            ret 0;
        }}
    cout<<-1;
    ret 0;
}

25.2.11 cf1003 c1(贪心,每个数都在符合要求的情况下尽量保持最小,无法满足就退出)

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
int n,m,b,a[200003];
int main()
{
    //ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        bool biao=1;
        int n,m;
        cin>>n>>m;
        repp(i,1,n)
        cin>>a[i];
        cin>>b;
        a[1]=min(a[1],b-a[1]);
        repp(i,2,n)
        {
            int t1=max(b-a[i],a[i]);
            int t2=min(b-a[i],a[i]);
            if(a[i-1]<=t2)a[i]=t2;
            else
            {
                if(a[i-1]>t1)
                {
                    biao=0;
                    break;
                }
                else
                a[i]=t1;
            }
        }
        if(biao)
        cout<<"YES"<<endl;
        else
        cout<<"No"<<endl;
    }
    ret 0;
}

25.2.13 P1048 采药

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int w[M],v[M];
int dp[M][M*10];
int main()
{
    //ios::sync_with_stdio(0);cin.tie(0);
    int t,m;
    cin>>t>>m;
    repp(i,1,m)
    {
        cin>>w[i]>>v[i];
    }
    repp(i,1,m)
    {
        repp(j,1,t)
        {
            dp[i][j]=dp[i-1][j];//先考虑不放入,继承(跨度较大)
            if(j>=w[i])//总时间大于这个时即可以尝试放入
            dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);//由子问题最优解递推,如果可以增值就放入
        }
    }
    cout<<dp[m][t];    
}

25.2.15

P1616 十年oi一场空,不开longlong见祖宗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
lld a[10003],b[10003],dp[10000003];
int main()
{
    lld t,m;
    cin>>t>>m;
    repp(i,1,m)
    cin>>a[i]>>b[i];
    repp(i,1,m)
    {
        repp(j,a[i],t)
        dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
    }
    cout<<dp[t];
    ret 0;
}