文章目录
T1：GCDtitlesolutioncode
T2：包含titlesolutioncode(正解code补充在上面了)
T3：前缀titlesolutioncode
T4：移动titlesolutioncode
T1：GCD
title
solution
非常水，看一眼就知道了 首先我们知道每一个数都有唯一的标准整数分解，即拆成若干个质数的幂的乘积 而我们又知道质数彼此互质，
g
c
d
(
)
=
1
gcd()=1
gcd()=1 所以就可以迅速反应到，如果一个数有
≥
2
\ge 2
≥2个质数因子，那么
g
c
d
gcd
gcd一定等于
1
1
1 否则
g
c
d
gcd
gcd就是唯一的质数因子 这样的话，需要寻找的特殊数一定是幂级递增
欧拉筛出
n
n
n以内的所有质数，然后进行幂级累乘，时间复杂度就是
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 最后加上没有被计算的数的个数即可，因为这些数每个都只会贡献
1
1
1
然后直接干掉这道水题
code
#include <cstdio>
#define ll long long
#define MAXN 10000000
int a
, b
, cnt
;
int prime
[MAXN
+ 5];
bool vis
[MAXN
+ 5];
ll ans
[MAXN
+ 5];
void sieve() {
for( int i
= 2;i
<= MAXN
;i
++ ) {
if( ! vis
[i
] )
vis
[i
] = 1, prime
[++ cnt
] = i
;
for( int j
= 1;i
* prime
[j
] <= MAXN
&& j
<= cnt
;j
++ ) {
vis
[i
* prime
[j
]] = 1;
if( i
% prime
[j
] == 0 ) break;
}
}
}
int main() {
sieve();
for( int i
= 1;i
<= MAXN
;i
++ )
ans
[i
] = 1;
for( int i
= 1;i
<= cnt
;i
++ ) {
int j
= 1;
while( 1ll * j
* prime
[i
] <= MAXN
) {
j
*= prime
[i
];
ans
[j
] = prime
[i
];
}
}
for( int i
= 1;i
<= MAXN
;i
++ )
ans
[i
] += ans
[i
- 1];
scanf( "%d %d", &a
, &b
);
printf( "%lld\n", ans
[b
] - ans
[a
- 1] );
return 0;
}
T2：包含
title
solution
这道题只要了解一点点枚举子集就能
A
C
AC
AC 直接暴力一个数枚举子集 自测大数据跑了1.3s以为会T，但是没想到交上去能跑过诶 好了——数据加强了，终于，我被卡掉了5分 正解就是每次随便丢掉任何一个
1
1
1，
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
#include <cstdio>
#define MAXN 1000005
int n
, m
;
bool vis
[MAXN
];
int main() {
scanf( "%d %d", &n
, &m
);
for( int i
= 1, x
;i
<= n
;i
++ ) {
scanf( "%d", &x
);
vis
[x
] = 1;
}
for( int i
= 1e6;i
;i
-- ) {
if( ! vis
[i
] ) continue;
for( int j
= 0;j
< 20;j
++ )
if( i
>> j
& 1 )
vis
[i
^ ( 1 << j
)] = 1;
}
for( int i
= 1, x
;i
<= m
;i
++ ) {
scanf( "%d", &x
);
if( vis
[x
] ) printf( "yes\n" );
else printf( "no\n" );
}
return 0;
}
code(正解code补充在上面了)
#include <cstdio>
#include <iostream>
using namespace std
;
#define MAXN 100005
#define MAXM 1000000
int n
, m
, cnt
, maxx
;
int a
[MAXN
];
bool vis
[MAXM
+ 5];
int main() {
scanf( "%d %d", &n
, &m
);
for( int i
= 1;i
<= n
;i
++ ) {
scanf( "%d", &a
[i
] );
maxx
= max( maxx
, a
[i
] );
}
for( int i
= 1;i
<= n
;i
++ ) {
int x
= a
[i
];
if( vis
[x
] ) continue;
vis
[x
] = 1, cnt
++;
if( cnt
== maxx
) continue;
for( int j
= x
;j
;j
= ( ( j
- 1 ) & x
) )
if( ! vis
[j
] ) {
vis
[j
] = 1;
cnt
++;
if( cnt
== maxx
) break;
}
}
for( int i
= 1, x
;i
<= m
;i
++ ) {
scanf( "%d", &x
);
if( vis
[x
] ) printf( "yes\n" );
else printf( "no\n" );
}
return 0;
}
T3：前缀
title
solution
大模拟！！无需多说慢慢敲，高精直接上
code
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std
;
#define int long long
#define mod 998244353
#define MAXN 100005
vector
< int > pos
[30];
char s
[MAXN
], t
[MAXN
];
int pi
[MAXN
][2], num
[MAXN
];
int n
, ans
;
int calc( int l
, int r
, int siz
, int len
) {
int cnt
= 0, ip
;
for( int i
= l
;i
<= r
;i
++ )
num
[i
- l
+ 1] = t
[i
] ^ 48;
for( ip
= r
- l
+ 1;! num
[ip
];ip
-- );
num
[ip
] --;
for( int i
= ip
+ 1;i
<= r
- l
+ 1;i
++ )
num
[i
] = 9;
int g
= 0, R
= 0;
for( int i
= 1;i
<= r
- l
+ 1;i
++ )
g
= R
* 10 + num
[i
], num
[++ cnt
] = g
/ siz
, R
= g
% siz
;
g
= 0;
for( int i
= cnt
;i
;i
-- )
g
+= len
* num
[i
], num
[i
] = g
% 10, g
/= 10;
for( int i
= 1;i
<= cnt
;i
++ )
g
= ( g
* 10 + num
[i
] ) % mod
;
ans
= ( ans
+ g
) % mod
;
return R
;
}
signed main() {
scanf( "%s", s
);
int lens
= strlen( s
);
for( int i
= 0;i
< lens
;i
++ )
pos
[s
[i
] ^ 96].push_back( i
), pi
[i
][0] = pos
[s
[i
] ^ 96].size() - 1;
for( int i
= 0;i
< lens
;i
++ )
pos
[0].push_back( i
), pi
[i
][1] = i
;
scanf( "%lld", &n
);
while( n
-- ) {
ans
= 0;
scanf( "%s", t
);
int lent
= strlen( t
);
int l
= 0, r
= 0, now
= lens
- 1, nxt
, flag
= 1, f
;
for( ;l
< lent
;l
= ++ r
) {
if( t
[l
] == '*' ) t
[l
] = 96, f
= 1;
else f
= 0;
int id
= t
[l
] ^ 96, siz
= pos
[id
].size();
if( ! siz
) { flag
= 0; break; }
if( pos
[id
][siz
- 1] <= now
) nxt
= pos
[id
][0];
else nxt
= *upper_bound( pos
[id
].begin(), pos
[id
].end(), now
);
if( now
< nxt
) ans
= ( ans
+ nxt
- now
) % mod
, now
= nxt
;
else ans
= ( ans
+ lens
+ nxt
- now
) % mod
, now
= nxt
;
if( l
+ 1 < lent
&& isdigit( t
[l
+ 1] ) )
for( ;r
+ 1 < lent
&& isdigit( t
[r
+ 1] );r
++ );
if( l
< r
) {
int R
= calc( l
+ 1, r
, siz
, lens
);
if( R
) {
nxt
= pos
[id
][( pi
[now
][f
] + R
) % siz
];
if( now
< nxt
) ans
= ( ans
+ nxt
- now
) % mod
, now
= nxt
;
else ans
= ( ans
+ lens
+ nxt
- now
) % mod
, now
= nxt
;
}
}
}
if( ! flag
) printf( "-1\n" );
else printf( "%lld\n", ans
);
}
return 0;
}
T4：移动
title
solution
用心出题，用脚造数据 有的代码不考虑后退错误贪心都能AC，还有暴力过去的 考虑将时间离散化，变成每个门在哪些时间段会打开，用
v
e
c
t
o
r
+
p
a
i
r
vector+pair
vector+pair存储 大概是
n
+
m
n+m
n+m个时间段
设
d
p
[
i
]
dp[i]
dp[i]表示最早到达 第
i
i
i个时间段对应的门 的时间 然后用类似最短路的方法去
d
p
dp
dp转移，每次可以向两边转移（前提是这个门和转移到达的门都打开）
code
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std
;
#define Pair pair < int, int >
#define inf 0x3f3f3f3f
#define MAXN 100005
struct node
{
int id
, x
, t
;
node() {}
node( int Id
, int X
, int T
) {
id
= Id
, x
= X
, t
= T
;
}
};
priority_queue
< node
, vector
< node
>, greater
< node
> > q
;
vector
< Pair
> G
[MAXN
], tmp
;
int n
, m
;
int id
[MAXN
<< 1], dp
[MAXN
<< 1];
bool cmp( Pair x
, Pair y
) {
return x
.first
< y
.first
;
}
bool operator > ( node x
, node y
) {
return x
.t
> y
.t
;
}
void calc( node p
, int x
) {
int r
= G
[p
.x
][p
.id
- id
[p
.x
]].second
;
int i
= lower_bound( G
[x
].begin(), G
[x
].end(), make_pair( p
.t
+ 1, 0 ) ) - G
[x
].begin() - 1;
if( G
[x
][i
].second
>= p
.t
+ 1 ) {
if( dp
[id
[x
] + i
] > p
.t
+ 1 ) {
dp
[id
[x
] + i
] = p
.t
+ 1;
q
.push( node( id
[x
] + i
, x
, p
.t
+ 1 ) );
}
}
i
++;
while( i
< G
[x
].size() && G
[x
][i
].first
<= r
+ 1 ) {
if( dp
[id
[x
] + i
] > G
[x
][i
].first
) {
dp
[id
[x
] + i
] = G
[x
][i
].first
;
q
.push( node( id
[x
] + i
, x
, G
[x
][i
].first
) );
}
i
++;
}
}
void solve() {
memset( dp
, 0x3f, sizeof( dp
) );
q
.push( node( 0, 0, 0 ) );
dp
[0] = 0;
while( ! q
.empty() ) {
node now
= q
.top(); q
.pop();
if( now
.t
> dp
[now
.id
] ) continue;
if( now
.x
> 0 ) calc( now
, now
.x
- 1 );
if( now
.x
<= n
) calc( now
, now
.x
+ 1 );
}
}
int main() {
scanf( "%d %d", &n
, &m
);
for( int i
= 1, a
, b
, c
;i
<= m
;i
++ ) {
scanf( "%d %d %d", &a
, &b
, &c
);
G
[a
].push_back( make_pair( b
, c
) );
}
G
[0].push_back( make_pair( 0, inf
) );
G
[n
+ 1].push_back( make_pair( 0, inf
) );
id
[1] = 1;
for( int i
= 1;i
<= n
;i
++ ) {
tmp
.clear();
sort( G
[i
].begin(), G
[i
].end(), cmp
);
int r
= -1;
for( int j
= 0;j
< G
[i
].size();j
++ ) {
if( G
[i
][j
].first
> r
+ 1 ) tmp
.push_back( make_pair( r
+ 1, G
[i
][j
].first
- 1 ) );
r
= max( r
, G
[i
][j
].second
);
}
tmp
.push_back( make_pair( r
+ 1, inf
) );
G
[i
] = tmp
;
id
[i
+ 1] = id
[i
] + G
[i
].size();
}
solve();
printf( "%d\n", dp
[id
[n
+ 1]] );
return 0;
}
