20230821比赛
T1 【佛山市选2013】树环转换 GMOJ 3230
Description
给定一棵N个节点的树,去掉这棵树的一条边需要消耗值1,为这个图的两个点加上一条边也需要消耗值1。树的节点编号从1开始。在这个问题中,你需要使用最小的消耗值(加边和删边操作)将这棵树转化为环,不允许有重边。
环的定义如下:
(1)该图有N个点,N条边。
(2)每个顶点的度数为2。
(3)任意两点是可达的。
树的定义如下:
(1)该图有N个点,N-1条边。
(2)任意两点是可达的。
Input
第一行是一个整数N代表节点的个数。
接下来N-1行每行有两个整数U, V(1 ≤ U, V ≤ N),表示双向边(U, V)
Output
输出把树转化为环的最小消耗值。
Sample Input
4 1 2 2 3 2 4
Sample Output
3
Data Constraint
对于20%的数据,有1≤N≤10。
对于100%的数据,有1≤N≤1000000。
题目大意:求把一棵树转为一个环的最小操作次数
比赛的想法:这不就是求树的直径嘛。对于一棵树,我们可以求出最长的直径 \(d\) ,然后用总边数 \(t = n - 1\) 得到要操作的边为:
\[2\times (t - d)+1 \]但是这个是错误的,因为有的边可能会多算——删掉自己又加上自己还不如不操作。
正解:不会dp,所以:
我们求出子树有多少条未解决的链,然后删去大于2条链的子树之间的联系(断边)。我们看作ans。最后记得输出 \(2\times ans + 1\) 因为要记录删掉和补上,最后还有一个成环的边。
#include <cstdio>
#define ll int // 这告诉我们,交之前记得算一下时空复杂度
ll n;
ll ans;
ll q[1000010][3];
ll head[1000010];
ll nxt[5000010];
ll to[5000010];
ll cnt;
void addEdge(ll u, ll v) {
++cnt;
to[cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
ll dfs(ll u, ll fa) {
ll size = 0; // 子树链的数量
for(ll i = head[u]; i; i = nxt[i]) {
ll v = to[i];
if(v == fa) continue;
size += dfs(v, u);
}
if(size < 2) return 1; // 没有链或只有一个链
if(fa == 0) { // 为根节点
ans += size - 2;
} else {
ans += size - 2 + 1; // 包括父节点
}
return 0;
}
int main() {
scanf("%d", &n);
for(ll i = 1; i < n; i++) {
ll u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
dfs(1, 0);
printf("%d", 2 * ans + 1);
return 0;
}
T2 【佛山市选2013】海明距离 GMOJ 3231
Description
对于二进制串a,b,他们之间的海明距离是指两个串异或之后串中1的个数。异或的规则为:
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0
计算两个串之间的海明距离的时候,他们的长度必须相同。现在我们给出N个不同的二进制串,请计算出这些串两两之间的最短海明距离。
Input
第一个数字是整数T(T≤10),代表数据的组数。
接下来有T组数据,每组数据的第一行是一个正整数N,代表不同的二进制串的个数。接下来是N行,每行都是一个二进制串(长度是5)。我们用数字(0-9)和字符(A-F)来表示这个二进制串。它代表这个二进制串的16进制码。例如,“12345”代表的二进制串为“00010010001101000101”。
Output
对于每个数据,请输出一个整数,即答案值。
Sample Input
2 2 12345 54321 4 12345 6789A BCDEF 0137F
Sample Output
6 7
Data Constraint
对于30%的数据有1≤N≤100
对于全部数据,有1≤N≤100000
先是打了暴力,然后因为之前做过一道二进制的题目——腿部挂件。题目是可持久化01Trie。
那么这道题会不会也是这个呢?后来发现并不是,所以我打了一个暴力——先枚举 \(1\) 个数字作为基准,然后dfs跑一遍 01Trie ,然后就行了。
后面发现不行,会TLE,怎么办呢?于是我加了一个剪枝——如果当前答案大于最小值就不遍历了。
成功AC。但是我感觉这不应该是正解。
正解应该是什么呢?应该是模拟退火,而且是LBSA(堆优化模拟退火)
下面我附上LBSA和我的代码:
我的暴力:
#include <cstdio>
#include <cstring>
#define ll long long
ll t, n;
bool a[100010][30];
ll son[700010][2];
ll cnt;
ll ans = 1e15;
inline ll min(ll x, ll y) {
return x > y ? y : x;
}
void dfs(ll x, ll p, ll r, ll tot) {
if(tot >= ans) return;
if(x == 20) {
if(tot == 0) return;
ans = min(ans, tot);
return;
}
if(a[r][x + 1] == 0) {
if(son[p][1]) {
dfs(x + 1, son[p][1], r, tot + (a[r][x + 1] != 1));
}
if(son[p][0]) {
dfs(x + 1, son[p][0], r, tot + (a[r][x + 1] != 0));
}
}
if(a[r][x + 1] == 1) {
if(son[p][0]) {
dfs(x + 1, son[p][0], r, tot + (a[r][x + 1] != 0));
}
if(son[p][1]) {
dfs(x + 1, son[p][1], r, tot + (a[r][x + 1] != 1));
}
}
}
inline char get() {
static char buf[10000000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,10000000,stdin),p1 == p2) ? EOF : *p1 ++;
}
inline ll read() {
ll x = 0;
char c = '.';
while(c < '0' || c > '9') c = get();
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ '0');
c = get();
}
return x;
}
inline ll readHex() {
ll x = 0;
char c = '.';
while(!((c >= '0' && c <= '9') || (c >='A' && c <= 'F'))) c = get();
while((c >= '0' && c <= '9') || (c >='A' && c <= 'F')) {
if(c >= '0' && c <= '9') x = (x << 4) + (c ^ '0');
else x = (x << 4) + (c - 'A' + 10);
c = get();
}
return x;
}
int main() {
// freopen("data.in", "r", stdin);
t = read();
while(t--) {
memset(son, 0, sizeof(son));
ans = 1e15;
cnt = 0;
n = read();
for(ll i = 1; i <= n; i++) {
ll x;
x = readHex();
for(ll j = 20; j >= 1; j--) {
a[i][j] = x&1;
x >>= 1;
}
ll p = 0;
for(ll j = 1; j <= 20; j++) {
if(!son[p][a[i][j]]) {
son[p][a[i][j]] = ++cnt;
}
p = son[p][a[i][j]];
}
}
for(ll i = 1; i <= n; i++) {
dfs(0, 0, i, 0);
}
printf("%lld\n", ans);
}
}
LBSA:
#include<cstdio>
#include<random>
#include<algorithm>
#include<ctime>
#include<cmath>
#define f(x) calc(a[x]^a[v])
using namespace std;
const int N = 1e5 + 2, P = 1 << 20, L = 100 + 2, K = 10, M = 10;
const double RND_MAX = 1ll << 32;
mt19937 rnd(time(NULL));
int T,tt,n,i,a[N],hs,f[P],ans;
double hp[L];
double RND() {
return rnd()/RND_MAX;
}
int calc(int x) {
if(f[x]<ans)
ans=f[x];
return f[x];
}
int Num(int x) {
return x<1?1:x>n?n:x;
}
void put(double x) {
hp[++hs]=x;
int k=hs;
while(k>1&&hp[k]>hp[k/2]) {
swap(hp[k],hp[k/2]);
k/=2;
}
return ;
}
double pop() {
double ret=hp[1];
hp[1]=hp[hs--];
int k=1;
while(k*2<=hs&&hp[k*2]>hp[k]||k*2+1<=hs&&hp[k*2+1]>hp[k]) {
int kk=k*2;
if(kk+1<=hs&&hp[kk+1]>hp[kk])
++kk;
swap(hp[k],hp[kk]);
k=kk;
}
return ret;
}
void LBSA(int v) {
hs=0;
int x=Num(v+rnd()%11-5);
double r=0.7;
for(int i=1; i<L; ++i) {
int y=Num(x+rnd()%11-5);
if(f(y)<f(x))
x=y;
put(-abs(f(y)-f(x))/log(r));
}
x=Num(v+rnd()%11-5);
for(int k=1; k<=K; ++k) {
double t=0,temp=hp[1];
int c=0;
for(int m=1; m<=M; ++m) {
int y=Num(x+rnd()%11-5);
if(f(y)<f(x))
x=y;
else {
double r=RND();
if(exp(-(f(y)-f(x))/temp)>r) {
t+=-(f(y)-f(x))/log(r);
++c;
x=y;
}
}
if(ans==1) return ;
}
if(c) {
pop();
put(t/c);
}
}
}
int main() {
f[0]=0;
for(i=1; i<P; ++i)
f[i]=f[i&(i-1)]+1;
f[0]=20;
scanf("%d",&T);
for(tt=1; tt<=T; ++tt) {
scanf("%d",&n);
for(i=1; i<=n; ++i)
scanf("%X",&a[i]);
stable_sort(a+1,a+n+1);
ans=20;
for(i=1; i<=n&&ans>1&&(double)clock()/CLOCKS_PER_SEC<0.998/T*tt; ++i)
LBSA(i);
printf("%d\n",ans);
}
return 0;
}
T3 【佛山市选2013】排列 GMOJ 3232
Description
一个关于n个元素的排列是指一个从{1, 2, …, n}到{1, 2, …, n}的一一映射的函数。这个排列p的秩是指最小的k,使得对于所有的i = 1, 2, …, n,都有p(p(…p(i)…)) = i(其中,p一共出现了k次)。
例如,对于一个三个元素的排列p(1) = 3, p(2) = 2, p(3) = 1,它的秩是2,因为p(p(1)) = 1, p(p(2)) = 2, p(p(3)) = 3。
给定一个n,我们希望从n!个排列中,找出一个拥有最大秩的排列。例如,对于n=5,它能达到最大秩为6,这个排列是p(1) = 4, p(2) = 5, p(3) = 2, p(4) = 1, p(5) = 3。
当我们有多个排列能得到这个最大的秩的时候,我们希望你求出字典序最小的那个排列。对于n个元素的排列,排列p的字典序比排列r小的意思是:存在一个整数i,使得对于所有j < i,都有p(j) = r(j),同时p(i) < r(i)。对于5来说,秩最大而且字典序最小的排列为:p(1) = 2, p(2) = 1, p(3) = 4, p(4) = 5, p(5) = 3。
Input
输入的第一行是一个整数T(T <= 10),代表数据的个数。
每个数据只有一行,为一个整数N。
Output
对于每个N,输出秩最大且字典序最小的那个排列。即输出p(1), p(2),…,p(n)的值,用空格分隔。
Sample Input
2 5 14
Sample Output
2 1 4 5 3 2 3 1 5 6 7 4 9 10 11 12 13 14 8
Data Constraint
对于40%的数据,有1≤N≤100。
对于所有的数据,有1≤N≤10000。
不会
T4 【佛山市选2013】排列 GMOJ 3229
Description
回文序列是指左右对称的序列。例如1 2 3 2 1是回文序列,但是1 2 3 2 2就不是。我们会给定一个N×M的矩阵,你需要从这个矩阵中找出一个P×P的子矩阵,使得这个子矩阵的每一列和每一行都是回文序列。
Input
第一行有两个正整数N, M。
接下来是n行,代表一个N×M的矩阵,矩阵的每个元素都是值不超过31415926的正整数。
Output
输出符合条件的子矩阵的最大大小P。
Sample Input
5 10 1 2 3 3 2 4 5 6 7 8 1 2 3 3 2 4 5 6 7 8 1 2 3 3 2 4 5 6 7 8 1 2 3 3 2 4 5 6 7 8 1 2 3 9 10 4 5 6 7 8
Sample Output
4
Data Constraint
对于20%数据 1 ≤ N, M ≤ 10
对于所有数据 1 ≤ N, M ≤ 300
正如我想,暴力跑一遍即可。
数据太水啦!
所以正解是什么呢?我觉得是马拉车这位(\(n^2\log n\))。
我的暴力:
#include <cstdio>
#define ll long long
using namespace std;
ll n, m, ans;
ll a[310][310];
inline ll min(ll x, ll y) {
return x < y?x:y;
}
inline ll read() {
ll x = 0;
char c = '.';
while(c < '0' || c > '9')
c = getchar();
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ '0');
c = getchar();
}
return x;
}
int main() {
n = read(), m = read();
for(ll i = 1; i <= n; i++) {
for(ll j = 1; j <= m; j++) {
a[i][j] = read();
}
}
for(ll p = min(n, m); p >= 1; p--) {
for(ll i = 1; i <= n - p + 1; i++) {
for(ll j = 1; j <= m - p + 1; j++) {
bool flag = true;
for(ll x = 1; x <= p; x++) {
for(ll y = 1; y <= p / 2; y++) {
if(a[i + x - 1][j + y - 1] != a[i + x - 1][j + p - y] || a[i + y - 1][j + x - 1] != a[i + p - y][j + x - 1]) {
flag = false;
break;
}
}
if(!flag) break;
}
if(flag) {
printf("%lld", p);
return 0;
}
}
}
}
printf("%lld", ans);
}
标签:return,比赛,20230821,ll,int,&&,ans,hp
From: https://www.cnblogs.com/znpdco/p/test20230821.html