第 46 屆 ICPC 國際大學生程式設計競賽亞洲區域賽（瀋陽）
有時候，很簡單的模板題，可能有人沒有做出來，（特指 I ），到時候一定要把所有的題目全部看一遍
B
輸入樣例
3 2
1 2 1
2 3 1
輸出樣例
1
說明
In the first sample case, the sequence [a1,a2,a3]=[0,1,0][a_1,a_2,a_3]=[0,1,0][a1,a2,a3]=[0,1,0] meets all the constraints and has the minimum sum of all the elements.
題解
這一道題目的關鍵就是要知道：異或操作的操作是位與位之間相互獨立的，所以就可以對於每一位進行單獨考慮。
如果這一位異或操作的結果是1那麼就說明該這兩位的取值必定相反，如果是0，那麼就說明這兩位的取值必定相同。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100020
int n, m;
//int a[N];
int fa[N*2];
struct {
int x, y, xo;
}b[N*2];
int get(int x)
{
if(fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
ll solve(int idx)//對於每一位進行操作
{
for(int i = 1; i <= 2*n; i++) fa[i] = i;
for(int i = 1; i <= m; i++)
{
int x = b[i].x;
int y = b[i].y;
int xo = ((b[i].xo)>>idx)&1;
if(xo == 1){
if(get(x) == get(y) ){
return -1;
}
else
{
fa[get(x)] = get(y+n);
fa[get(y)] = get(x+n);
}
}
else if(xo == 0)
{
if(get(x) == get(y+n) ){
return -1;
}else{
fa[get(x)] = get(y);
fa[get(y+n)] = get(x+n);
}
}
}
map<int, pair<int, int> >mp;
for(int i = 1; i <= n; i++)
{
//cout << "n:" << n << "\n";
int id = min(get(i), get(i+n));
//cout << id << " " << get(i) << "\n";
if(get(i) == id){
mp[id].first++;
}
else {
mp[id].second++;
}
}
ll ans = 0;
for(auto &x : mp)
{
ans += min(x.second.first, x.second.second);
//cout << x.first << " "<< x.second.first << " " << x.second.second << "\n";
}
return ans;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].xo);
}
ll ans = 0;
for(int i = 0; i <= 30; i++)
{
ll ret;
ret = solve(i);
if(ret == -1){
puts("-1");
return 0;
}
ans += ret << i;
}
printf("%lld", ans);
system("pause");
return 0;
}
E
On November 6, 2021, the Chinese team Edward Gaming (EDG) defeated the South Korea team DWG KIA (DK) to win the 2021 League of Legends World championship in Reykjavík, Iceland, lifting the Summoner’s Cup for the first time in their history.
While both teams had looked dominant（佔主導地位） throughout the competition, DK arguably（可以論證的） had the advantage. The team hadn’t lost a single game until they reached the semi-finals and was the only team to make it out of the Group Stage without a single defeat. They were clearly the team to beat.
EDG had given them a hit at the very first game of the final. The game started with a well-executed gank in the bot lane by EDG for the first blood. Later, EDG took every single Drake and the Baron, and ultimately destroyed the DK’s Nexus after 35 minutes.
But DK wouldn’t leave it unanswered. They maintained an advantage throughout the second game. Not even the incredible Baron steal by EDG’s legendary jungler, Jiejie , could help the team.
The third game turned out to be a difficult one. EDG seems to have control over more resources during the first 30 minutes. However, DK constantly killed every single dragon, and they finally took down the Nexus with the Hand of Baron.
In the fourth game, EDG had rethought their approach and took higher precedence in the control over dragons. The strategy had immediately taken effect, and they won the game after 33 minutes.
All things came down to the last game of the finals. Initially, DK took up the first dragon without much resistance from EDG. Shortly after, EDG picked first blood as DK took the Herald. Everything was fairly even at that moment. The balance finally started to tip in EDG’s favor during a team fight in the mid-lane, with EDG killing DK’s midlaner Showmaker before they had a chance to respond. The fight finally ended up with four kills and one death for EDG. They snowballed their advantage and finally secured the trophy.
The triumph of the Worlds 2021 made EDG the first team from LPL to win both the Mid-Season Invitational and the World Championship. You have just written a long string to celebrate this great victory. How many occurrences of “edgnb” as a continuous substring are there in the long string? Please write a program to count the number.
輸入描述:
The only line contains a nonempty string, which consists of no more than 200000 lowercase Latin letters, ‘a’ to ‘z’.
輸出描述:
Output a line containing a single integer, indicating the number of occurrences of “edgnb” in the given string.
edgnb
1
並沒有必要閱讀
#include <bits/stdc++.h>
using namespace std;
char a[300000];
int main()
{
scanf("%s", a+1);
int len = strlen(a+1);
int ans = 0;
for(int i = 1; i <= len; i++)
{
if(a[i] == 'e' && a[i+1] == 'd' && a[i+2] == 'g' && a[i+3] == 'n' && a[i+4] == 'b')
ans ++;
}
cout << ans;
return 0;
}
F
輸入樣例1
4
aacc
輸出樣例1
bbaa
輸入樣例2
3
aca
輸出樣例2
ba
題解
暴力枚舉
#include <bits/stdc++.h>
using namespace std;
#define N 1010
int n;
char a[N];
bool vis[128];
int cnt;
int ans[N];
int tmp[N];
int num[128];
bool check(int s)
{
int i = 1;
while(ans[i] == tmp[i] && i < N) i++;
if(tmp[i] > ans[i]) return true;
return false;
}
int main()
{
scanf("%d", &n);
scanf("%s", a+1);
for(int i = 1; i <= n; i++)
{
memset(vis, 0, sizeof(vis));
cnt = 0;
for(int j = i; j >= 1; j--)
{
if(!vis[a[j]]){
cnt++;
vis[a[j]] = true;
num[a[j]] = cnt;
}
tmp[j] = num[a[j]];
}
if(check(i)) {
for(int j = 1; j <= i; j++)
ans[j] = tmp[j];
}
// printf("DEBUG");
// for(int j = 1; j <= i; j++)
// {
// putchar('a'+tmp[j] - 1);
// }
// puts("");
}
int len = 1;
while(ans[len] != 0) len ++;
for(int i = 1; i < len; i++) putchar(ans[i]+'a'-1);
puts("");
system("pause");
return 0;
}
H
輸入樣例1
5 6
1 2 1
1 3 2
1 4 3
4 3 4
4 5 5
2 5 6
輸出樣例1
21
輸入樣例2
6 5
1 2 4
2 3 1
3 4 3
4 5 2
5 6 5
輸出樣例2
12
輸入樣例3
5 5
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
輸出樣例3
14
更為詳細的題解見此處//blog.csdn.net/li_wen_zhuo/article/details/121633394
常規的思維是先輸入圖G，然後通過手段構建出L(G)，然後求圖裡面的最大匹配。
現在我們反過來，把要求帶到G圖中。
L（G）中的一條邊就相當於是G中的具有相同端點的兩條邊。同時，所選擇的邊不重複。
經過轉化之後，經過奇思妙想：
如果原圖G中具有偶數條邊，那麼就可以選擇所有的邊。
證明：對於原圖，是無環的，並且原圖可以分為若干個連通塊，每一個連通塊連通並且無環，那麼就是樹。對於偶數個邊的樹：
（按照從葉子到根的方法進行考慮）
如果要是有一個節點具有偶數個兒子，那麼這偶數個與兒子相連接的邊兩兩組合。然後這一個節點變為葉子節點。
如果要是有一個節點具有奇數個兒子，那麼這偶數個與兒子相連接的邊兩兩組合。剩下的兒子，這一個節點，這一個節點的父親所連接的邊構成 具有相同端點的兩條邊
如果要是具有奇數條邊，那麼一定至少有一條邊是無法進行匹配的。
刪除一條邊，按照常理所，剩下的就可以全部匹配了。但是可能這一條邊恰恰是割邊，並且刪除這一條邊以後形成的兩個新的連通塊中全部是奇數條邊，那麼就相當於有三條邊無法匹配，所以損失過大，故是橋的這一條邊還是不刪為妙！
可以使用並查集來查看是否在同一個連通塊里
由於對於每一個連通塊都有可能出現有邊無法匹配的情況，所以把邊的權值從大到小進行排序（貪心），優先安排權值大的邊。
注意：圖論不一定是需要進行建圖的，還可以僅僅存放點！
#include <bits/stdc++.h>
using namespace std;
#define N 300020
int fa[N], val[N];//與並查集結合使用
int n, m;
struct edge{
int x, y, w;
bool operator <(const edge &o){//從大到小進行排列
return w > o.w;
}
}a[N];
int get(int x)
{
if(x == fa[x]) return x;
return fa[x] = get(fa[x]);//BUG1:沒有寫 fa[x] =
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].w);
}
sort(a+1, a+1+m);//BUG2:sort(a+1, a+1+n);
for(int i = 1; i <= n; i++){
fa[i] = i;
//val[i] = 0;如果是多組數據，就需要！
}
long long ans = 0;
for(int i = 1; i <= m; i++)
{
int x = get(a[i].x), y = get(a[i].y), w = a[i].w;
if(x == y){
if(val[x]){
ans += val[x] + w;
val[x] = 0;
}else{
val[x] = w;
}
}
else {//x != y
if(val[x] && val[y])//兩邊都是奇數，要選這一條邊
{
ans += w + max(val[x], val[y]);
fa[x] = y;
val[y] = min(val[x], val[y]);
}
else if(!val[x] && !val[y])//兩邊是偶數，可以選這一條邊，也可以不選。但是邊是按照從大到小來進行排序的，所以暫時不選這一條邊是最好的策略
{
fa[x] = y;
val[y] = w;
}
else {
ans += max(val[x], val[y])+w;
fa[x] = y;
val[y] = 0;
}
}
}
cout << ans;
return 0;
}
I
輸入樣例
2
-1 0 0 -1
0 1 -1 0
1 0 0 1
0 -1
-1 0 -1 0
0 1 0 -1
1 0 1 0
0 -1
輸出樣例
1.000000000000000 0.000000000000000
0.000000000000000 1.000000000000000
In the first sample case we have$ f(z)=iz$, and in the second sample case we have \(f(z)=1/z\).
題解&程式碼
沒有什麼好說的，敲就完了！
但是要注意一點：C++裡面本來就有 複數這一個東西！
但是C++裡面的複數的等於號有一點點陰間，所以等於根據精度判斷一下就好了
#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
const double eps = 1e-6;
using namespace std;
class Complex{
public:
double x, y;
Complex(){
x = 0;
y = 0;
}
Complex(double a, double b){
x = a;
y = b;
}
};
Complex operator + (const Complex &a, const Complex &b) {
return Complex( a.x + b.x, a.y + b.y );
}
Complex operator - (const Complex &a, const Complex &b) {
return Complex( a.x - b.x, a.y - b.y );
}
Complex operator * (const Complex &a, const Complex &b) {
return Complex( a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);
}
Complex operator / (const Complex &a, const Complex &b) {
return Complex( (a.x*b.x+a.y*b.y)/(b.x*b.x + b.y*b.y), (a.y*b.x-a.x*b.y)/(b.x*b.x + b.y*b.y) );
}
bool operator == (const Complex &a, const Complex &b) {
if(fabs(a.x-b.x) < eps && fabs(a.y-b.y) < eps) return true;
else return false;
}
Complex c[5][5], b[5];
int main()
{
int T;
cin >> T;
while(T--)
{
double tx, ty;
Complex z0, z1, z2, z3, w1, w2, w3, w0;
scanf("%lf%lf", &tx, &ty);
z1 = Complex(tx, ty);
scanf("%lf%lf", &tx, &ty);
w1 = Complex(tx, ty);
scanf("%lf%lf", &tx, &ty);
z2 = Complex(tx, ty);
scanf("%lf%lf", &tx, &ty);
w2 = Complex(tx, ty);
scanf("%lf%lf", &tx, &ty);
z3 = Complex(tx, ty);
scanf("%lf%lf", &tx, &ty);
w3 = Complex(tx, ty);
scanf("%lf%lf", &tx, &ty);
z0 = Complex(tx, ty);
Complex m, n;
m = (w1-w2)/(z1-z2);
n = (w1-m*z1);
if(m*z3+n == w3){//如果分母為0
w0 = m*z0 + n;
printf("%.15lf %.15lf\n", w0.x, w0.y);
continue;
}
Complex zero(0, 0);
c[1][1] = z1, c[1][2] = zero - w1, c[1][3] = Complex(1, 0);
c[2][1] = z2, c[2][2] = zero - w2, c[2][3] = Complex(1, 0);
c[3][1] = z3, c[3][2] = zero - w3, c[3][3] = Complex(1, 0);
b[1] = z1*w1;
b[2] = z2*w2;
b[3] = z3*w3;
//高斯的錯
for(int i = 1; i <= 3; i++)
{
for(int j = i; j <= 3; j++)
{
if(!(c[j][i]==zero)){
for(int k = 1; k <= 3; k++) swap(c[i][k], c[j][k]);
swap(b[i], b[j]);
}
}
for(int j = 1; j <= 3; j++){
if(i == j) continue;
Complex rate = c[j][i] / c[i][i];
for(int k = i; k <= 3; k++)
{
c[j][k] = c[j][k] - c[i][k] * rate;
}
b[j] = b[j] - b[i] * rate;
}
}
Complex ans = (b[1]/c[1][1]*z0 + b[3]/c[3][3])/(z0+(b[2]/c[2][2]));
printf("%.15lf %.15lf\n", ans.x, ans.y);
}
system("pause");
return 0;
}
J
輸入樣例
6
1234 2345
1234 0123
1234 2267
1234 3401
1234 1344
1234 2468
輸出樣例
1
1
4
5
1
4
這一道題目我們對先採用了大模擬，發現考慮的情況太多，然後又採用了暴力搜索。
參考題解：//zhuanlan.zhihu.com/p/563484871
第 J 題
就如其中所說的，如果每一次都進行暴力，那麼就有可能超時。
所以需要轉變一下思路。
- 這其實就類似於高中物理的轉化參考系，如果把最終的密碼視為參考系，那麼所有的測試樣例就會全部轉化為一種情況，搜索一次就可以滿足所有的情況。
- 在搜索的時候採用BFS策略（可以求得最短的步數）
#include <bits/stdc++.h>
using namespace std;
map<string, int> mp;//其實使用數組也可以，但是把一個字元串映射為一個整數比較麻煩，so
queue<string> q;
void bfs()
{
q.push("0000");
mp["0000"] = 0;
while(!q.empty())
{
string s = q.front();
q.pop();
//if(mp.count(s)) continue;
for(int i = 0; i < 4; i++)
{
for(int j = i; j < 4; j++)
{
string up = s;
string down = s;
for(int k = i; k <= j; k++)
{
up[k] = (up[k]-'0'+1)%10+'0';
down[k] = (down[k]-'0'-1+10)%10+'0';
}
if(!mp.count(up)) {
mp[up] = mp[s] + 1;
q.push(up);
}
if(!mp.count(down)) {
mp[down] = mp[s] + 1;
q.push(down);
}
}
}
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(0);//淺淺優化一下
//但是在這樣搞了以後，就不要使用printf()了，可能導致輸出順序不一樣然後寄掉
bfs();
int T;
cin >> T;
while(T--)
{
string a, b;
cin >> a >> b;
for(int i = 0; i < 4; i++){
b[i] = ((a[i]-'0')-(b[i]-'0')+10)%10+'0';
}
cout << mp[b] << "\n";
}
return 0;
}
