[noi.ac省选模拟赛]第10场题解集合
2024-08-29 21:02:43
题目
比赛界面。
T1
不难想到，对于一个与\(k\)根棍子连接的轨道，我们可以将它拆分成\(k+1\)个点，表示这条轨道不同的\(k+1\)段。
那么，棍子就成为了点与点之间的边。可以发现，按照棍子连边之后，我们一定可以得到一些链。假设每条轨道的最后一段作为链头，查询实际上就是查询所在链的链头。
使用 LCT 或 Splay 维护这些链即可，时间\(O(n\log_2n)\)。
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 2e6 + 5;
const int INF = 0x3f3f3f3f;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
void swapp( _T &x, _T &y )
{
_T t = x; x = y, y = t;
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
vector<int> bar[MAXN];
int ch[MAXN][2], fa[MAXN];
int id[MAXN], lef[MAXN], rig[MAXN];
int beg[MAXN], bel[MAXN];
int N, M, Q, nsiz;
bool chk( const int x ) { return ch[fa[x]][1] == x; }
bool isrt( const int x ) { return ch[fa[x]][0] ^ x && ch[fa[x]][1] ^ x; }
bool nrt( const int x ) { return ! isrt( x ); }
void rotate( const int x )
{
if( ! x || isrt( x ) ) return ;
int y = fa[x], z = fa[y], side = chk( x ), son = ch[x][! side];
if( z && nrt( y ) ) ch[z][chk( y )] = x; ch[x][! side] = y, ch[y][side] = son;
if( son ) fa[son] = y; fa[y] = x, fa[x] = z;
}
void splay( const int x )
{
for( int y ; nrt( x ) ; rotate( x ) )
if( nrt( y = fa[x] ) )
rotate( chk( y ) == chk( x ) ? y : x );
}
void access( int x ) { for( int y = 0 ; x ; x = fa[y = x] ) splay( x ), ch[x][1] = y; }
int query( int x )
{
access( x ), splay( x );
while( ch[x][0] ) x = ch[x][0];
splay( x ); return x;
}
int main()
{
int tmp;
read( N ), read( M );
for( int i = 1 ; i <= M ; i ++ ) read( id[i] ), bar[id[i]].push_back( i ), bar[id[i] + 1].push_back( i );
for( int i = 1 ; i <= N ; i ++ )
{
tmp = bar[i].size(), beg[i] = nsiz + 1;
for( int j = 0, ref ; j < tmp ; j ++ )
{
ref = bar[i][j], ++ nsiz;
bel[nsiz] = i;
if( id[ref] == i ) lef[ref] = nsiz;
else rig[ref] = nsiz;
}
bel[ ++ nsiz] = i;
}
for( int i = 1 ; i <= M ; i ++ ) fa[lef[i]] = rig[i] + 1, fa[rig[i]] = lef[i] + 1;
int opt, x, u, v;
read( Q );
while( Q -- )
{
read( opt ), read( x );
if( opt == 1 )
{
u = lef[x], v = rig[x];
access( u ), splay( u ), fa[ch[u][0]] = 0, ch[u][0] = 0;
access( v ), splay( v ), fa[ch[v][0]] = 0, ch[v][0] = 0;
access( u + 1 ), splay( u + 1 ), fa[u + 1] = u, ch[u][0] = u + 1;
access( v + 1 ), splay( v + 1 ), fa[v + 1] = v, ch[v][0] = v + 1;
}
if( opt == 2 ) write( bel[query( beg[x] )] ), putchar( '\n' );
}
return 0;
}
T2
题解给出了有关欧拉路的做法：
如果所有点的度数都是偶数，那么我们只需要找一条欧拉回路，然后间隔着删边就好。否则，我们可以通过连边使得奇点变偶点，然后求一条欧拉回路，这时图被若干条链覆盖，我们同样可以是间隔着对每条链进行删边操作。
然鹅我并不想鸟它
实际上，由于题目保证有解，那么......大概，只需要删除所有可删除的边就可以了。
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 1e6 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
vector<int> G[MAXN];
int fr[MAXN], to[MAXN];
int d[MAXN], T[MAXN];
int N, M;
bool used[MAXN];
void addE( const int from, const int to )
{
G[from].push_back( to ), d[from] ++;
}
int main()
{
int p, u, v;
read( N ), read( M );
for( int i = 1 ; i <= M ; i ++ ) read( fr[i] ), read( to[i] ), addE( fr[i], i ), addE( to[i], i );
for( int i = 1 ; i <= N ; i ++ ) T[i] = ceil( 1.0 * d[i] / 2 );
for( int i = 1 ; i <= N ; i ++ )
for( int j = 0 ; j < G[i].size() ; j ++ )
if( ! used[p = G[i][j]] )
{
u = fr[p], v = to[p];
if( d[u] == T[u] || d[v] == T[v] ) continue;
used[p] = true, d[u] --, d[v] --;
}
for( int i = 1 ; i <= M ; i ++ ) write( ! used[i] ), putchar( i == M ? '\n' : ' ' );
return 0;
}
T3
奇怪的计算几何题目。
可以发现性质：
\[\text{点}P\text{不被染色}\Leftrightarrow\text{点}P\text{可以看到至少}\frac n 2\text{条边}
\]
\]
如果可以看到\(\frac n 2\)条边，就说明\(P\)在这些边与它们的对边的覆盖范围之外。又由于这\(\frac n 2\)条边一定在凸包上是按端点连续的，不可能有一组对边，因此\(P\)就无法被覆盖。多于\(\frac n 2\)的可以通过抛弃对边缩减到\(\frac n 2\)条。
怎么计算\(P\)能看到多少条边呢？我们考虑，先找出一个它能看到的点，再进行向左向右的二分，就可以找出\(P\)能看到的端点的区间，进而找到边的区间。
怎么找到最初的点呢？很简单，我们随机一组对边，如果\(P\)可以被它们覆盖，我们就可以直接输出。否则， 4 个点中肯定有至少一个\(P\)可以看到，我们判断一下就可以了。
计算只涉及叉积，在使用 __int128 的情况下不存在精度问题。
好烦的题，谁写谁恶心
#include <cstdio>
#include <cstdlib>
typedef __int128 LL;
#define int LL
const LL e = 1;
const int MAXN = 1e5 + 5;
template<typename _T>
inline void read ( _T &x )
{
x = 0; int f = 1; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
x *= f;
}
struct point
{
LL x, y;
point() { x = y = 0; }
point( const LL X, const LL Y ) { x = X, y = Y; }
};
struct vector
{
LL x, y;
vector() { x = y = 0; }
vector( const LL X, const LL Y ) { x = X, y = Y; }
vector( point S, point T ) { x = T.x - S.x, y = T.y - S.y; }
LL operator * ( const vector &b ) const { return x * b.y - y * b.x; }
};
point P[MAXN];
int N, Q;
int go( const int c, const int step ) { return ( c + step - 1 + N ) % N + 1; }
bool visible( const point Q, const int i )
{
LL t1 = vector( P[i], Q ) * vector( Q, P[i % N + 1] );
LL t2 = vector( P[i], Q ) * vector( Q, P[( i - 2 + N ) % N + 1] );
return t1 > 0 || t2 < 0;
}
signed main()
{
srand( 998244353 );
LL A, B; point R;
int l, r, mid, lef, rig, sta;
int T, lst = 0;
read( T ), read( N );
for( int i = 1 ; i <= N ; i ++ ) read( P[i].x ), read( P[i].y );
read( Q );
int hal = N / 2, t1, t2;
while( Q -- )
{
read( A ), read( B );
if( T ) A ^= e * lst * lst * lst;
if( T ) B ^= e * lst * lst * lst;
R = point( A, B );
int p = rand() % N + 1, q = ( p + N / 2 - 1 ) % N + 1;
t1 = vector ( P[p], R ) * vector ( R, P[p % N + 1] );
t2 = vector ( P[q % N + 1], R ) * vector ( R, P[q] );
if ( ! t1 || ! t2 || ( t1 < 0 && t2 > 0 ) )
{
puts ( "DA" ), ++ lst;
continue;
}
sta = visible ( R, p ) ? p : q;
l = 0, r = N - 1;
while( l < r )
{
mid = l + r + 1 >> 1;
if( visible ( R, ( sta - mid - 1 + N ) % N + 1 ) ) l = mid;
else r = mid - 1;
}
rig = l;
l = 0, r = N - 1;
while( l < r )
{
mid = l + r + 1 >> 1;
if( visible ( R, ( sta + mid - 1 ) % N + 1 ) ) l = mid;
else r = mid - 1;
}
lef = l;
int len = lef + rig;
if( len >= hal ) puts( "NE" );
else lst ++, puts( "DA" );
}
return 0;
}
小结
计算几何知识为 0 弱爆了，需要加强。
虽然 T1 一眼想到方法，然而花了很长时间找合适的数据结构，说明自己还不熟悉。
最新文章
- maven 错误解决办法集
- poj 2325 Persistent Numbers
- hibernate 问题集
- R语言实战读书笔记(三)图形初阶
- Spark RDD概念学习系列之细谈RDD的弹性（十六）
- javascript设计模式3
- 3.SQL*Plus命令
- 支持SMTP邮箱介绍
- nginx 通过rsyslog发日志 rsyslog服务器挂掉 日志丢失问题
- 设计模式(Facade)状态(注意事项)
- iOS 注册密码加密 添加了时间戳 遇到的问题...
- 基于MATLAB的人脸识别算法的研究
- qt 布局
- PuTTY 串口调试，为普通用户增加访问串口设备权限
- hibernate多生成一个外键以及映射文件中含有<list-index>标签
- MySql 在cmd下的学习笔记 —— 有关多表查询的操作（内连接，外连接，交叉连接）
- OPENSSL编程 第二十章 椭圆曲线
- Canny边缘检测算法的一些改进
- windows下git的使用
- SSH框架的基本整合