A. Hello, ACMer!
这题就是找到hznu的个数
#include<bits/stdc++.h>
using namespace std;
int32_t main() {
string s;
cin >> s;
int cnt = 0;
for( int i = 0 ; i + 3 < s.size() ; i ++ ){
if( s[i] == 'h' && s[i+1] == 'z' && s[i+2] == 'n' && s[i+3] == 'u' )
cnt ++;
}
cout << cnt << "\n";
return 0;
}
B. New String
这题是给出一个排序，表示的字母的相对顺序。
把字符串转化然后在排序就好。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
struct node{
string a ;
string b;
node() { a = "" , b = "";}
friend bool operator < ( node x , node y ){
return x.a < y.a;
}
} s[N];
int main(){
string st;
char mp[30];
cin >> st;
for( int i = 0 ; i < 26 ; i ++ ){
mp[ st[i] - 'a' ] = i+'a';
}
int n , m;
cin >> n;
for( int i = 1 ; i <= n ; i ++ )
{
cin >> s[i].b;
for( auto it : s[i].b )
s[i].a += mp[ it - 'a' ];
}
sort( s + 1 , s + 1 + n );
cin >> m;
cout << s[m].b;
}
C. Check Problems
有无穷多个问题和n个人，每个人会从\(a_i\)个问题开始解决，每一秒只能解决一个问题，一个问题也只能没解决一次，问t秒后一共可以解决多少个问题。
从题目发现\(a_i\) 是递增的，同时\(a_{i+1}-a_i\)也是递增的。那么我们令\(b_i=a_{i+1}-a_{i}\)那么当\(t<a_i\)是时i个人解决了t个问题，当\(t\ge a_i\) 时第i个人解决了\(b_i\)个问题。这样的话对于每一个询问二分一下分界线的位子就可以\(O(1)\)的算出解决了多少问题。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5;
int n , a[N] , b[N];
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
int32_t main() {
n = read();
for( int i = 1 ; i <= n ; i ++ )
a[i] = read();
for( int i = 1 ; i < n ; i ++ )
b[i] = a[i+1] - a[i];
for( int t , x , m = read() ; m ; m -- ){
t = read();
x = lower_bound( b+1 , b+n , t ) - b;
cout << a[x] - a[1] + ( n - x + 1 ) * t << "\n";
}
return 0;
}
D. Tree Problem
给一个树，每次询问一个点，问树上有多少对点的简答路径经过了这个点。
对于每一个，我们把她当成树的根，那么他的任意一个子树中任意选择两个点，这两个点的简单路径都不经过这个点。
所以要统计出每一个点的每一个子树的大小，这个用一遍dfs就可以了。然后在套一些组合数就好了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
vector< int > e[N] , son[N] ;
int sz[N] , n , sum , res[N];
bool vis[N];
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
void dfs( int u ){
vis[u] = sz[u] = 1;
for( auto v : e[u] ){
if( vis[v] ) continue;
dfs(v);
sz[u] += sz[v];
son[u].push_back( sz[v] );
}
son[u].push_back( n - sz[u] );
}
int32_t main() {
n = read();
for( int i = 1 , u , v ; i < n ; i ++ )
u = read() , v = read() , e[u].push_back(v) , e[v].push_back(u);
dfs( 1 );
sum = (n * n - n ) / 2;
for( int i = 1 ; i <= n ; i ++ ){
res[i] = sum;
for( auto it : son[i] )
if( it >= 2 ) res[i] -= ( it * it - it ) / 2;
}
for( int m = read() , x; m ; m -- ){
x = read();
cout << res[x] << "\n";
}
return 0;
}
E. Easy Problem
有AB两个人，他们每次都会向相同的地方移动，但是他们中的某个人遇到边界或者障碍是不会继续走的。问最少多少步他们就会相遇。
因为n很小，所以直接bfs就好了。然后加一点记忆化剪枝。
#include<bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int,int> node;
const int N = 55;
bitset<N> mp[N];
int n;
const int dx[] = { 0 , 0 , 1 , -1 } , dy[] = { 1 , -1 , 0 , 0 };
queue< node > q;
map< node , int > dep;
bool check( int x , int y ){
if( x < 0 || y < 0 || x >= n || y >= n ) return false;
if( mp[x][y] ) return false;
return true;
}
int main(){
cin >> n;
int ax , ay , bx , by;
for( int i = 0 ; i < n ; i ++ ){
string s;
cin >> s;
for( int j = 0 ; j < n ; j ++ )
if( s[j] == '*' ) mp[i][j] = 1;
else if( s[j] == 'a' ) ax = i , ay = j;
else if( s[j] == 'b' ) bx = i , by = j;
}
dep[ { ax , ay , bx , by } ] = 0;
q.push( { ax , ay , bx , by } );
while( q.size() ){
auto [ ax , ay , bx , by ] = q.front() ; q.pop();
if( ax == bx && ay == by ){
cout << dep[ { ax , ay , bx , by } ] << "\n";
return 0;
}
for( int i = 0 ; i < 4 ; i ++ ){
int fax = ax +dx[i] , fay = ay + dy[i] , fbx = bx + dx[i] , fby = by + dy[i];
if( !check( fax , fay ) ) fax = ax , fay = ay;
if( !check( fbx , fby ) ) fbx = bx , fby = by;
if( dep.find( { fax , fay , fbx , fby } ) != dep.end() ) continue;
q.push( { fax , fay , fbx , fby } ) ; dep[ { fax , fay , fbx , fby } ] = dep[ { ax ,ay , bx , by } ] + 1;
}
}
cout << "no solution\n";
return 0;
}