2025 成大賽心得文

1
import sys
2
input=sys.stdin.readline
3
MOD=10**9+7
4
n,k=map(int,input().split())
5
A=[0]*k
6
LEN=[0]*k
7

8
for i in range(k):
9
    a,l,r=map(int,input().split())
10
    A[i]=a
11
    LEN[i]=r- l+1
12

13
ORD=list(range(k))
14
ORD.sort(key=lambda i: A[i])
15

16
SUF=[0]*(k+1)
17
for t in range(k-1,-1,-1):
18
    i=ORD[t]
19
    SUF[t]=(SUF[t+1]+A[i]*LEN[i])%MOD
20

21
q=int(input())
22
ans=0
23
for _ in range(q):
24
    S=int(input())
25
    l,r=0,k
26
    while l<r:
27
        m=(l+r)//2
28
        if A[ORD[m]]>S:
29
            r= m
30
        else:
31
            l=m+1
32
    ans=(ans+SUF[l])%MOD
33
print(ans)

1
#pragma GCC optimize("Ofast","unroll-loops","no-stack-protector")
2
#include <iostream>
3
#include <utility>
4
#define f first
5
#define s second
6
using namespace std;
7

8
pair<int, int> arr[(int)1E7 + 7];
9
long long ans, cnt, tmp;
10

11
int main()
12
{
13
    ios::sync_with_stdio(0); cin.tie(0);
14

15
     int N, l, r; cin >> N;
16
     for(int i = 0; i < N; i++) {
17
       cin >> l >> r;
18
       arr[l].f++;
19
       arr[r].s++;
20
     }
21

22

23
     for(int i = 0; i < (int)1E7; i++) {
24
       tmp = cnt;
25
       if (arr[i].f) cnt += arr[i].f;
26
       if (arr[i].s) cnt -= arr[i].s;
27

28
       ans += cnt * cnt;
29
     }
30
     cout << ans << '\n';
31

32
    return 0;
33
}

1
#pragma GCC optimize("Ofast","unroll-loops","no-stack-protector")
2
#include <iostream>
3
#include <queue>
4
#include <utility>
5
#define f first
6
#define s second
7
using namespace std;
8

9
queue< pair<int, int> > qu;
10
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}, maxa, tmpa;
11

12
int main()
13
{
14
    ios::sync_with_stdio(0); cin.tie(0);
15

16
     int n, m; cin >> n >> m;
17
     int grid[n+2][m+2][2], d = 1;
18
     char c;
19
     for(int i = 1; i <= n; i++) {
20
       for(int j = 1;j <= m; j++) {
21
         cin >> c;
22
         if (c == '#') grid[i][j][0] = 0;
23
         else grid[i][j][0] = 1;
24
         grid[i][j][1] = 0, grid[0][j][0] = 0, grid[n+1][j][0] = 0, grid[0][j][1] = 0, grid[n+1][j][1] = 0;
25
       }
26
       grid[i][0][0] = 0, grid[i][m+1][0] = 0, grid[i][0][1] = 0, grid[i][m+1][1] = 0;
27
     }
28

29
     maxa = 0, tmpa = 0;
30
     for(int i = 1; i <= n; i++) {
31
       for(int j = 1; j <= m; j++) {
32
         if (grid[i][j][0] && grid[i][j][1] != d) {
33
           tmpa++;
34
           grid[i][j][1] = d;
35
           for(int k = 0; k < 4; k++) {
36
             if (grid[i + dx[k]][j + dy[k]][0] && grid[i + dx[k]][j + dy[k]][1] != d) {
37
               qu.push({i + dx[k], j + dy[k]});
38
             }
39
           }
40

41
           //bfs
42
           while(!qu.empty()) {
43
             auto tmpP  = qu.front(); qu.pop();
44
             if (grid[tmpP.f][tmpP.s][1] == d) continue;
45
             grid[tmpP.f][tmpP.s][1] = d;
46

47
             tmpa++;
48
             for(int k = 0; k < 4; k++) {
49
               if (grid[tmpP.f + dx[k]][tmpP.s + dy[k]][0] && grid[tmpP.f + dx[k]][tmpP.s + dy[k]][1] == (d ^ 1)) {
50
                 qu.push({tmpP.f + dx[k], tmpP.s + dy[k]});
51
               }
52
             }
53
        }
54
           maxa = max(maxa, tmpa), tmpa = 0;
55
         }
56
       }
57
     }
58

59
     int q, x, y; cin >> q;
60
     while(q--) {
61
       d++, tmpa = 1;
62
       cin >> x >> y;
63
       x++, y++;
64
       grid[x][y][0] = 1, grid[x][y][1] = d;
65

66
       for(int i = 0; i < 4; i++) {
67
         if (grid[x + dx[i]][y + dy[i]][0] && grid[x + dx[i]][y + dy[i]][1] != d) {
68
           qu.push({x + dx[i], y + dy[i]});
69
         }
70
       }
71
    while(!qu.empty()) {
72
         auto tmpP  = qu.front(); qu.pop();
73
         if (grid[tmpP.f][tmpP.s][1] == d) continue;
74
         grid[tmpP.f][tmpP.s][1] = d;
75

76
         tmpa++;
77
         for(int k = 0; k < 4; k++) {
78
           if (grid[tmpP.f + dx[k]][tmpP.s + dy[k]][0] && grid[tmpP.f + dx[k]][tmpP.s + dy[k]][1] != d) {
79
             qu.push({tmpP.f + dx[k], tmpP.s + dy[k]});
80
           }
81
         }
82
       }
83

84
       maxa = max(maxa, tmpa);
85
       cout << maxa << '\n';
86
     }
87

88
    return 0;
89
}

1
import sys
2
input=sys.stdin.readline
3
n,m=map(int,input().split())
4
grid=[list(input().strip()) for _ in range(n)]
5
def dfs(i,j,visited):
6
    stack=[(i,j)]
7
    area=0
8
    while stack:
9
        x,y=stack.pop()
10
        if x<0 or x>=n or y<0 or y>=m:
11
            continue
12
        if visited[x][y] or grid[x][y] != '@':
13
            continue
14
        visited[x][y]=True
15
        area += 1
16
        stack.append((x+1,y))
17
        stack.append((x-1,y))
18
        stack.append((x,y+1))
19
        stack.append((x,y-1))
20
    return area
21

22
q=int(input())
23
for _ in range(q):
24
    x,y=map(int,input().split())
25
    if grid[x][y] !='@':
26
        grid[x][y]='@'
27
    visited=[[False] * m for _ in range(n)]
28
    max_area=0
29
    for i in range(n):
30
        for j in range(m):
31
            if grid[i][j]=='@' and not visited[i][j]:
32
                max_area=max(max_area,dfs(i,j,visited))
33
    print(max_area)

1
import sys
2
input=sys.stdin.readline
3
def find(x):
4
    if p[x] != x:
5
        p[x]=find(p[x])
6
    return p[x]
7
def union(x,y):
8
    rx=find(x)
9
    ry=find(y)
10
    if rx==ry:
11
        return sz[rx]
12
    if sz[rx]<sz[ry]:
13
        rx,ry=ry,rx
14
    p[ry]=rx
15
    sz[rx] +=sz[ry]
16
    return sz[rx]
17

18
n,m=map(int,input().split())
19
grid=[list(input().strip()) for _ in range(n)]
20
total=n*m
21

22
p=list(range(total))
23
sz=[1]*total
24

25
active=[[False]*m for _ in range(n)]
26
max_area=0
27
dire=[(1,0),(-1,0),(0,1),(0,-1)]
28

29
for i in range(n):
30
    for j in range(m):
31
        if grid[i][j]=='@':
32
            active[i][j]=True
33
            idx=i*m+j
34
            for di,dj in dire:
35
                ni,nj=i+di,j+dj
36
                if 0<=ni<n and 0<=nj<m and active[ni][nj]:
37
                    new_area=union(idx,ni*m+nj)
38
                    max_area=max(max_area,new_area)
39

40
q=int(input())
41
for _ in range(q):
42
    x,y=map(int,input().split())
43
    if not active[x][y]:
44
        active[x][y]=True
45
        grid[x][y]='@'
46
        idx=x*m+y
47
        curr_area=1
48
        for di,dj in dire:
49
            ni,nj=x+di,y+dj
50
            if 0<=ni<n and 0<=nj<m and active[ni][nj]:
51
                curr_area=union(idx,ni*m+nj)
52
        max_area=max(max_area,curr_area)
53
    print(max_area)

1
import sys
2
def f(n,player):
3
    player.sort(key=lambda x:(-x[0],x[1]))
4
    group=[]
5
    i=0
6
    while i < len(player):
7
        pos=player[i][0]
8
        min_s=player[i][1]
9
        j=i+ 1
10
        while j < len(player) and player[j][0] ==pos:
11
            min_s=min(min_s,player[j][1])
12
            j+=1
13
        t=(n -pos)/ min_s
14
        group.append((pos,t))
15
        i=j
16

17
    count=0
18
    current_time= -1.0
19
    for pos,t in group:
20
        if t > current_time:
21
            count+=1
22
            current_time=t
23
    return count
24

25
input=sys.stdin.readline
26
n,m=map(int,input().split())
27

28
male=[]
29
female=[]
30
for _ in range(m):
31
    s,p,g=input().split()
32
    s,p,g=int(s),int(p),int(g)
33
    if g ==0:
34
        male.append((p,s))
35
    else:
36
        female.append((p,s))
37

38
ans=0
39
ans+=f(n,male)
40
ans+=f(n,female)
41
print(ans)