周二
周二
A
模拟出以最小公倍数为周期的结果
#include<iostream>
#define pii pair<int,int>
using namespace std ;
const int N = 250 ;
pii mp[5] = {{2,3} , {0,3} , {1,4} , {4,2} , {0,1}};
int n , na , nb , a[N] , b[N] , ansa , ansb , resa , resb , tn ;
int gcd(int a , int b) {
return b ? gcd( b , a % b ) : a ;
}
int main () {
ios :: sync_with_stdio(false) ;
cin.tie(0) , cout.tie(0) ;
cin >> n >> na >> nb ;
for(int i=0; i<na; i++) {
cin >> a[i] ;
}
for(int i=0; i<nb; i++) {
cin >> b[i] ;
}
int t = na * nb / gcd( na , nb ) ;
tn = n % t ;
for(int i=0; i<tn; i++) {
if(a[i%na] != b[i%nb]) {
if(mp[a[i%na]].first == b[i%nb] || mp[a[i%na]].second == b[i%nb]) resa ++ ;
else resb ++ ;
}
}
if(n <= t) {
cout << resa << ' ' << resb ;
}
else {
for(int i=0; i<t; i++) {
if(a[i%na] != b[i%nb]) {
if(mp[a[i%na]].first == b[i%nb] || mp[a[i%na]].second == b[i%nb]) ansa ++ ;
else ansb ++ ;
}
}
int temp = n / t ;
cout << ansa * temp + resa << ' ' << ansb * temp + resb ;
}
return 0 ;
}
B
无向连通图 G 有 n 个点，n−1 条边。点从 1 到 n 依次编号,编号为 i 的点的权值为 W i，每条边的长度均为 1。图上两点(u,v) 的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对 (u,v)，若它们的距离为 2，则它们之间会产生W v×W u的联合权值。 请问图G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
由于有n-1条边所以距离为2的情况有两种：任一结点的父结点和其子节点，该结点的所有任意两个子节点之间；求任意子节点之间的联合权值时遍历求会超时，但可以利用公式简化到只用遍历一遍
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define int long long
/*
8
1 2
1 3
1 4
3 5
3 6
4 7
7 8
8 7 6 5 4 3 2 1
*/
using namespace std ;
const int mod = 10007 , N = 2e5 + 10 ;
int n , idx , e[N*2] , ne[N*2] , h[N] , w[N] , fa[N] , ans , sum ;
bool book[N] ;
void add ( int a , int b ) {
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
void dfs(int u , int f) {
fa[u] = f ;
for(int i=h[u]; ~i; i=ne[i]) {
int j = e[i] ;
if(j != f) {
dfs( j , u ) ;
}
}
}
void dfs(int u) {
vector<int> v ;
book[u] = true ;
for(int i=h[u]; ~i; i=ne[i]) {
int j = e[i] ;
if(!book[j]) {
if(fa[u]) {
ans = max ( ans , w[j] * w[fa[u]] ) ;
sum = ( sum + w[j] * w[fa[u]] ) % mod ;
sum = ( sum + w[j] * w[fa[u]] ) % mod ;
}
dfs(j) ;
v.push_back(w[j]) ;
}
}
// if(u == 1) {
// for(int i=0; i<v.size(); i++) {
// cout << v[i] << ' ' ;
// }
// cout << endl ;
// }
sort ( v.begin(), v.end() ) ;
if(v.size() >= 2) {
int t = v.size() ;
ans = max ( ans , v[t-1] * v[t-2] ) ;
int res = 0 ;
int tsum = 0 ;
for(int i=0; i<v.size(); i++) {
res = (v[i] + res) % mod ;
tsum = ( tsum + v[i] * v[i] % mod ) % mod ;
}
res %= mod ;
res = res * res % mod ;
res = (res - tsum) % mod ;
sum = ( sum + res ) % mod ;
}
//
// for(int i=0; i<v.size(); i++) {
// for(int j=i+1; j<v.size(); j++) {
// ans = max ( ans , w[v[i]] * w[v[j]] ) ;
// sum = ( sum + w[v[i]] * w[v[j]]) % mod ;
// }
// }
}
signed main () {
ios :: sync_with_stdio(false) ;
cin.tie(0) , cout.tie(0) ;
memset ( h , -1, sizeof h) ;
cin >> n ;
for(int i=1; i<=n-1; i++) {
int u , v ; cin >> u >> v ;
add ( u , v ) ;
add ( v , u ) ;
}
for(int i=1; i<=n; i++) cin >> w[i] ;
dfs( 1 , 0 ) ;
// for(int i=1; i<=n; i++) {
// cout << " i = " << i << " fa = " ;
// cout << fa[i] << endl ;
// }
dfs(1) ;
// sum = ( sum + sum ) % mod ;
cout << ans << ' ' << (sum + mod ) % mod ;
return 0 ;
}
D 二维前缀和
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std ;
const int N = 150 ;
int d , n , mp[N][N], cnt ;
ll ans ;
signed main () {
ios :: sync_with_stdio(false) ;
cin.tie(0) , cout.tie(0) ;
cin >> d >> n ;
for(int i=1; i<=n; i++) {
int x , y , k ;
cin >> x >> y >> k ;
mp[x][y] += k ;
}
for(int i=0; i<=128; i++) {
for(int j=0; j<=128; j++) {
ll res = 0 ;
for(int x=max(0,i-d); x<=min(128,i+d); x++) {
for(int y=max(0,j-d); y<=min(128,j+d); y++) {
res += mp[x][y] ;
}
}
// cout << "res = " << res << endl ;
if(res > ans){
ans = res ;
cnt = 1 ;
}
else if(res == ans) cnt ++ ;
}
}
cout << cnt << ' ' << ans ;
return 0 ;
}E
在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
路径上的所有点的出边所指向的点都直接或间接与终点连通。 在满足条件 1 的情况下使路径最短。 注意：图 G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入格式 第一行有两个用一个空格隔开的整数
n 和 m，表示图有 n 个点和 m 条边。接下来的 m 行每行2 个整数 ,x,y，之间用一个空格隔开，表示有一条边从点 x 指向点y。
最后一行有两个用一个空格隔开的整数 ,s,t，表示起点为 s，终点为 t。
输出格式 输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出−1。
由于边权为1，先反向bfs建图，找出所有和终点连通的点，然后再bfs从符合题目条件的点中找出最短路径
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std ;
const int N = 1e4 + 10 , M = 2e5 + 10 ;
int n , m , idx , e[M*2] , ne[M*2] , h[N] , hs[N] , st , ed , ans ;
queue<int> q ;
bool book[N] , flag , mark[N] ;
void add(int h[] , int a , int b ) {
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
bool check(int u) {
for(int i=h[u]; ~i; i=ne[i]) {
int j = e[i] ;
if(!mark[j]) return false ;
}
return true ;
}
int main () {
ios :: sync_with_stdio(false) ;
cin.tie(0) , cout.tie(0) ;
memset( h , -1 , sizeof h ) ;
memset( hs , -1 , sizeof hs) ;
cin >> n >> m ;
while( m -- ) {
int x , y ;
cin >> x >> y ;
add ( h , x , y ) ;
add ( hs , y , x ) ;
}
cin >> st >> ed ;
q.push(ed) ;
mark[ed] = true ;
while( q.size() ) {
int t = q.front() ;
//cout << t << endl ;
q.pop() ;
for(int i=hs[t]; ~i; i=ne[i]) {
int j = e[i] ;
if(!mark[j]) {
q.push(j) ;
mark[j] = true ;
}
}
}
queue<pair<int,int>> que ;
que.push({ed,0}) ;
while( que.size() ) {
auto t = que.front() ;
// cout << t << endl ;
que.pop() ;
if( t.first == st ) {
flag = true ;
ans = t.second ;
break ;
}
int now = t.first ;
for(int i=hs[now]; ~i; i=ne[i]) {
int j = e[i] ;
if(!book[j] && mark[j]) {
if(check(j)) que.push({j,t.second + 1}) ;
book[j] = true ;
}
}
}
if(flag) cout << ans ;
else cout << -1 ;
return 0 ;
}