서론 손재주가 없고 머리도 나쁘니까, 저는 그냥 그런 사람입니다.
T1 [SHOI2016] 무작위 시열 (강화판) 문제 백준(약화판) 강화판 데이터에는 (a_i=0)인 경우가 있으며, 시험에서 통과하지 못한 이유는 코드의 한 부분에서 -1 처리를 빠뜨렸기 때문입니다. 그러나 0이 없는 경우는 통과할 수 있었기 때문에 테스트 케이스에는 문제가 없었습니다.
강화판 코드
//12252024832524
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
const int MOD = 1e9 + 7;
int n,m;
int arr[MAXN];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Print1(T x)
{
if(x > 9) Print1(x/10);
putchar(x%10^48);
}
TT void Print(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Print1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int qpow(int x,int y)
{
int ret = 1;
while(y){if(y & 1) ret = 1ll * ret * x % MOD;x = 1ll * x * x % MOD;y >>= 1;}
return ret;
}
#define lc (x<<1)
#define rc (x<<1|1)
int seg[MAXN << 2],val[MAXN << 2],lazy[MAXN << 2],PRE = 1;
int Ad(int x){if(x >= MOD) x -= MOD; if(x < 0) x += MOD; return x;}
void up(int x){seg[x] = Ad(seg[lc] + seg[rc]);}
void calc(int x,int val){seg[x] = 1ll * seg[x] * val % MOD;lazy[x] = 1ll * lazy[x] * val % MOD;}
void down(int x)
{
if(lazy[x] == 1) return;
calc(lc,lazy[x]);
calc(rc,lazy[x]);
lazy[x] = 1;
}
void Build(int x,int l,int r)
{
lazy[x] = 1;
if(l == r)
{
PRE = 1ll * PRE * arr[l] % MOD;
if(l < n) seg[x] = 2ll * PRE * qpow(3,n-l-1) % MOD;
else seg[x] = PRE;
return;
}
int mid = (l+r) >> 1;
Build(lc,l,mid); Build(rc,mid+1,r);
up(x);
}
void Mul(int x,int l,int r,int ql,int qr,int v)
{
if(ql <= l && r <= qr)
{
calc(x,v);
return;
}
down(x);
int mid = (l+r) >> 1;
if(ql <= mid) Mul(lc,l,mid,ql,qr,v);
if(mid+1 <= qr) Mul(rc,mid+1,r,ql,qr,v);
up(x);
}
int Query(int x,int l,int r,int ql,int qr)
{
if(ql > qr) return 0;
if(ql <= l && r <= qr) return seg[x];
down(x);
int mid = (l+r) >> 1,ret = 0;
if(ql <= mid) ret += Query(lc,l,mid,ql,qr);
if(mid+1 <= qr) ret += Query(rc,mid+1,r,ql,qr);
return Ad(ret);
}
set<int> zeros;
set<int>::iterator it;
int main()
{
n = Read(); m = Read();
for(int i = 1;i <= n;++ i)
{
arr[i] = Read();
if(!arr[i]) arr[i] = 1,zeros.insert(i);
}
Build(1,1,n);
zeros.insert(n+1);
for(int i = 1;i <= m;++ i)
{
int pos = Read(),v = Read();
if(!v) zeros.insert(pos);
else
{
it = zeros.lower_bound(pos);
if((*it) == pos) zeros.erase(it);
Mul(1,1,n,pos,n,1ll * qpow(arr[pos],MOD-2) * v % MOD);
arr[pos] = v;
}
it = zeros.begin();
Print(Query(1,1,n,1,*it-1),'\n');//이전에 여기에 -1이 없었습니다
}
return 0;
}
해설 문제의 특성을 분석하면 덧셈과 뺄셈이 가능하면 답에 기여하지 않음을 발견할 수 있습니다. 따라서 덧셈과 뺄셈이 없는 경우, 즉 곱셈만 고려하면 됩니다. 직접 시그먼트 트리를 사용하여 관리하면 됩니다. 0이 있는 경우 중간에서 끊는 것과 같으며, 답을 구할 때 전체적으로 계산하지 않습니다.
T2 NCPC 5회 A문제 포탈 문제 NCPC 제가 본 문제는 아마도 수정된 버전일 수 있으므로 문제 의미가 다를 수 있지만, 본질은 동일합니다.
해설 먼저 배송 지점과 수령 지점을 모두 반드시 방문해야 하는 지점으로 간주합니다. 이 문제에서 영감을 얻어 현재 사람이 어디에 있는지 기록할 필요가 없다는 것을 알 수 있습니다. 왜냐하면 항상 어떤 체크포인트에 있기 때문입니다. 그런 다음 특성을 분석하면 포탈을 사용하려면 현지에서 포탈을 열면 시작점이 되므로, 포탈의 위치만 기록하면 됩니다. 그러면 (O(n^2k)) DP가 가능해집니다. 배열을 롤링할 수 있지만 필수는 아니며, 롤링하지 않으면 공간을 두 배로 해야 합니다.
롤링하지 않은 코드
//12252024832524
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 305;
const LL INF = 1ll << 60;
int n,m,s;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Print1(T x)
{
if(x > 9) Print1(x/10);
putchar(x%10^48);
}
TT void Print(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Print1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
LL dist[MAXN][MAXN],dp[MAXN << 1][MAXN];//작업 i, 포탈이 j에 있음
int location[MAXN << 1];
int main()
{
n = Read(); m = Read(); s = Read() << 1;
for(int i = 1;i <= n;++ i)
for(int j = 1;j <= n;++ j)
if(i^j) dist[i][j] = INF;
for(int i = 1,u,v;i <= m;++ i)
u = Read(),v = Read(),dist[u][v] = dist[v][u] = Min(dist[u][v],Read());
for(int k = 1;k <= n;++ k)
for(int i = 1;i <= n;++ i)
for(int j = 1;j <= n;++ j)
dist[i][j] = Min(dist[i][j],dist[i][k]+dist[k][j]);
for(int i = 1;i <= s;++ i) location[i] = Read();
memset(dp,0x3f,sizeof(dp));
for(int i = 1;i <= n;++ i) //포탈 위치를 나타내는 변수
for(int j = 1;j <= n;++ j)//중간 포탈
dp[1][i] = Min(dp[1][i],dist[1][j]+dist[i][j]+Min(dist[i][location[1]],dist[j][location[1]]));
for(int i = 2;i <= s;++ i)
for(int j = 1;j <= n;++ j)
{
dp[i][j] = Min(dp[i][j],dp[i-1][j]+dist[location[i-1]][location[i]]);
for(int k = 1;k <= n;++ k)
dp[i][k] = Min(dp[i][k],dp[i-1][j]+dist[j][k]+Min(dist[k][location[i]],dist[j][location[i]])),//포탈을 통해 포탈을 배치
dp[i][k] = Min(dp[i][k],dp[i-1][j]+dist[location[i-1]][k]+Min(dist[k][location[i]],dist[j][location[i]]));//포탈을 배치하려고 걸어가고, 포탈을 통해 현재 지점으로 이동
}
LL ans = INF;
for(int i = 1;i <= n;++ i) ans = Min(ans,dp[s][i]);
Print(ans);
return 0;
}
T3 NCPC 5회 B문제 그래프 문제 NCPC 이 문제도 위와 동일합니다.
해설 문제의 특성을 분석하면 최소 XOR 스패닝 트리 문제임을 알 수 있습니다. 하지만 저는 이 문제를 해결하지 못하고, (O(n^2))의 (\tt Prim) 알고리즘을 사용하여 70점을 얻었습니다. 정답은 개선된 (\tt Boruvka) 알고리즘이며, 각 라운드 작업에서 (O(m))을 열거하는 대신 (O(n\log_2a_i))로 딕셔너리 트리나 가중치 선분 트리에서 쿼리할 수 있습니다. 동적 연결성을 유지하고 최소 XOR을 쿼리해야 하므로, 유니온 파인드 + 선분 트리 병합을 사용하고 주석 트리 쿼리의 아이디어로 구현하면 됩니다. 또한 상수가 작고 코드가 짧은 방법은 가중치 분할입니다. (\log_2a_i) 레이어를 고려하고, 각 레이어에서 현재 레이어를 0과 1 두 부분으로 나눕니다. 명백히 레이어가 높을수록 우리가 연결하려는 간선은 적어야 하므로, 좌우 하위 트리가 각각 연결된 후 좌우 0과 1 부분은 단 1개의 간선만 연결하면 됩니다. 연결할 간선은 반쪼리를 Trie에 삽입하고 나머지 쪼리는 쿼리하면 됩니다. 두 방법의 시간 복잡도는 동일하며, 모두 (O(n\log_2n\log_2a_i))입니다.
선분 트리 병합의 큰 상수 방법
//12252024832524
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 200005;
const int INF = 1 << 30;
int n;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Print1(T x)
{
if(x > 9) Print1(x/10);
putchar(x%10^48);
}
TT void Print(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Print1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int head[MAXN],etot;
struct edge
{
int to,w,nxt;
}e[MAXN << 1];
void Add_Edge(int x,int y,int z)
{
e[++etot].to = y;
e[etot].w = z;
e[etot].nxt = head[x];
head[x] = etot;
}
void Add_Double_Edge(int x,int y,int z)
{
Add_Edge(x,y,z);
Add_Edge(y,x,z);
}
int depth[MAXN],value[MAXN];
void dfs(int x)
{
for(int i = head[x]; i ;i = e[i].nxt)
if(!depth[e[i].to])
depth[e[i].to] = depth[x] + 1,value[e[i].to] = value[x] ^ e[i].w,dfs(e[i].to);
}
bool visited[MAXN];
int order[MAXN],parent[MAXN];
bool cmp(int x,int y){return value[x] < value[y];}
int findSet(int x)
{
if(parent[x]^x) parent[x] = findSet(parent[x]);
return parent[x];
}
int rt[MAXN],tot,current;
int ch[MAXN*60][2],siz[MAXN*60],ID[MAXN*60];
void Add(int &x,int v,int rk)
{
if(!x) x = ++tot;
++siz[x];
if(rk < 0) {ID[x] = current;return;}
bool bit = v >> rk & 1;
Add(ch[x][bit],v,rk-1);
}
int merge(int x,int y)
{
if(!x || !y) return x|y;
siz[x] += siz[y];
ch[x][0] = merge(ch[x][0],ch[y][0]);
ch[x][1] = merge(ch[x][1],ch[y][1]);
return x;
}
void unionSet(int u,int v)
{
u = findSet(u); v = findSet(v);
if(u^v) parent[v] = u,rt[u] = merge(rt[u],rt[v]);
}
int MIN[MAXN],CID[MAXN],original;
void Query(int lst,int x,int v,int rk)
{
if(v >= MIN[current]) return;
if(rk < 0)
{
CID[current] = ID[lst];
MIN[current] = v;
return;
}
bool bit = value[original] >> rk & 1;
if(siz[ch[lst][bit]] - siz[ch[x][bit]]) Query(ch[lst][bit],ch[x][bit],v,rk-1);
else Query(ch[lst][bit^1],ch[x][bit^1],v|(1<<rk),rk-1);
}
int main()
{
n = Read();
for(int i = 1,u,v;i < n;++ i)
{
u = Read()+1,v = Read()+1;
Add_Double_Edge(u,v,Read());
}
depth[1] = 1,dfs(1);
for(int i = 1;i <= n;++ i) value[i] = Read();
for(int i = 1;i <= n;++ i) order[i] = parent[i] = i,MIN[i] = INF;
int cnt = n;
sort(order+1,order+n+1,cmp);
for(int i = 2;i <= n;++ i)
if(value[order[i]] == value[order[i-1]])
unionSet(order[i-1],order[i]),--cnt;
for(int i = 1;i <= n;++ i)
if(findSet(i) == i)
current = i,Add(rt[i],value[i],29),Add(rt[0],value[i],29);
LL ans = 0;
while(cnt > 1)
{
for(int i = 1;i <= n;++ i)
{
current = findSet(i); original = i;
Query(rt[0],rt[current],0,29);
}
for(int i = 1;i <= n;++ i)
{
if(MIN[i] < INF && findSet(i) != findSet(CID[i]))
{
unionSet(i,CID[i]);
ans += MIN[i];
MIN[i] = INF;
--cnt;
}
}
}
Print(ans);
return 0;
}