A dreamstart的催促
快速幂模板题
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 10000019;
int n , ans = 0;
int ksm( ll x , ll y )
{
ll res = 1;
while( y )
{
if( y & 1 ) res = ( res * x ) % mod;
y >>= 1;
x = x * x % mod;
}
return res;
}
int main()
{
cin >> n;
for( int i = 1 , x ; i <= n ; i ++ )
{
cin >> x;
ans = ( ans + ksm( x , i ) ) % mod;
}
cout << ans << endl;
return 0;
}
B TRDD got lost again
BFS题目,一次跳两格即可如果跳一格有障碍,则不能跳这一步
#include<bits/stdc++.h>
using namespace std;
const int N = 6005;
const int dx[] = { 1 , -1 , 0 , 0 } , dy[]={ 0 , 0 , 1 , -1 };
int n , m , tx , ty , nx , ny , fx , ffx , fy , ffy ;
int step ;
bool vis[N][N];
queue< pair< pair< int, int> , int > > q;
int main()
{
cin >> n >> m;
getchar();
n = 2 * n + 1 , m = 2 * m + 1;
char ch;
for( int i = 1 ; i <= n ; i ++ )
{
for( int j = 1 ; j <= m ; j ++ )
{
ch = getchar();
if( ch == 'S' ) q.push( { { i , j } , 1 } ) , vis[i][j] = 1;
else if( ch == 'T' ) tx = i , ty = j;
else if( ch != ' ' ) vis[i][j] = 1;
}
getchar();
}
while( !q.empty() )
{
nx = q.front().first.first , ny = q.front().first.second , step = q.front().second ; q.pop();
if( nx == tx && ny == ty ) { cout << step << endl; return 0; }
for( int i = 0 ; i < 4 ; i ++ )
{
fx = nx + dx[i] , fy = ny + dy[i] , ffx = nx + ( dx[i] << 1 ), ffy = ny + ( dy[i] << 1 );
if( ffx < 1 || ffy < 1 || ffx > n || ffy > m ) continue;
if( vis[fx][fy] || vis[ffx][ffy] ) continue;
q.push( { { ffx , ffy } , step + 1 } ) , vis[ffx][ffy] = 1;
}
}
cout << "TRDD Got lost...TAT\n";
}
C Company
DFS统计子树大小即可
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n , k , son[N];
bool vis[N];
vector< int > e[N];
int read()
{
int x = 0 , ch = getchar();
while( ch < '0' || ch > '9' ) ch = getchar();
while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
return x;
}
void dfs( int x )
{
vis[x] = 1;
for( auto v : e[x] )
{
if( vis[v] ) continue;
dfs( v ) , son[x] += son[v];
}
return ;
}
int main()
{
n = read() , k = read();
for( int i = 1 , x ; i <= n ; i ++ ) x = read() , son[i] = ( x <= k );
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);
for( int i = 1 ; i <= n ; i ++ ) printf("%d " , son[i] );
printf("\n");
}
D >A->B->C-
签到题,由于环的大小为三才成立,根本不用DFS
#include <bits/stdc++.h>
using namespace std;
int n , a[5005] , b , c ;
bool v[5005];
int main()
{
cin >> n;
for( int i = 1 ; i <= n ; i ++ ) cin >> a[i];
for( int i = 1 ; i <= n ; i ++ )
{
b = a[i];
c = a[b] ;
if( i == b || b == c || c == i ) continue;
if( i == a[c] )
{
cout << "YES\n";
return 0;
}
}
cout << "NO\n";
return 0;
}
E PPY的字符串
模拟题,重复做n次就好,字符转数字的可以用数组表示
#include <bits/stdc++.h>
using namespace std;
int n;
string a , b;
const char num[] = { '0' , '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9'};
int main()
{
cin >> a >> n;
n --;
while( n -- )
{
for( int i = 0 , j , t ; i < a.size() ; i = j )
{
for( j = i + 1 ; a[i] == a[j] ; j ++ );
t = j - i;
while( t ) b += num[ ( t % 10 ) ] , t /= 10;
b += a[i];
}
a = b , b = "";
}
cout << a.size() << " " << a << endl;
}
F 集训队脱单大法:这是一道只能由学姐我自己出数据的水题
前缀和,枚举切开的点
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n , a[N] , x[N] , y[N] , res ;
int main()
{
cin >> n;
for( int i = 1 ; i <= n ; i ++ ) cin >> a[i];
for( int i = 1 ; i <= n ; i ++ ) x[i] = max( x[ i - 1 ] , a[i] );
for( int i = n ; i >= 1 ; i -- ) y[i] = max( y[ i + 1 ] , a[i] );
for( int i = 1 ; i < n ; i ++ ) res = max( res , abs( x[i] - y[ i + 1 ] ) );
cout << res << endl;
return 0;
}
G 不想再WA了
DP题目,但是难得写,就随手写了个搜索,担心TLE,就打了个表,但实际上我的DFS似乎可以直接过
#include <bits/stdc++.h>
using namespace std;
int res[] ={ 0 , 3 , 8 , 21 , 55 , 144 , 377 , 987 , 2584 , 6765 , 17711 };
int main()
{
int t , n;
cin >> t;
for( int i = 1 ; i <= t ; i ++ )
{
cin >> n;
cout << res[n] << endl;
}
}
下面是DFS打表格代码
#include <bits/stdc++.h>
using namespace std;
int n , cnt;
int dfs( int dep , int last )
{
if( dep == n + 1 )
{
cnt ++;
return 0;
}
for( int i = 1 ; i <= 3 ; i ++ )
{
if( i == 1 && last == 3 ) continue;
dfs( dep + 1 , i );
}
}
int main()
{
for( n = 1 ; n <= 10 ; n ++ )
{
cnt = 0;
dfs( 1 , 0 );
cout << cnt << endl;
}
}
H Ricky’s RealDan’s Ricky
只有当只有一堆,且为偶数时Ricky
才会赢,不然其他任何情况RealDan
都可以通过有限次操作把一堆娃娃变成奇数。此时Ricky
则无法取胜
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n , a[N];
void slove()
{
cin >> n;
for( int i = 1 ; i <= n ; i ++ ) cin >> a[i];
if( n == 1 && a[1] % 2 == 0 ) puts("Ricky is Winner");
else puts("RealDan is Winner");
}
int main()
{
int t;
cin >>t;
while( t -- ) slove();
}
I 小A的期末作业
签到题目
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
for( int i = 0 ; i < n ; i ++ )
{
for( int j = 1 ; j <= i ; j ++ ) cout << ' ';
for( int j = 1 ; j <= n ; j ++ ) cout << '*';
cout << '\n';
}
for( int i = n - 2 ; i >= 0 ; i -- )
{
for( int j = 1 ; j <= i ; j ++ ) cout << ' ';
for( int j = 1 ; j <= n ; j ++ ) cout << '*';
cout << '\n';
}
return 0;
}
J 怪盗基德 & 月之瞳宝石
排序找到每个星体最近的能源体,并取最大值,查找能源体可以用二分
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
long long n , m , a[N] , b[N] , res = 0;
int main()
{
cin >> n >> m;
for( int i = 1 ; i <= n ; i ++ ) cin >> a[i];
for( int i = 1 ; i <= m ; i ++ ) cin >> b[i];
sort( b + 1 , b + 1 + m );
for( int i = 1 , l ; i <= n ; i ++ )
{
l = lower_bound( b + 1 , b + 1 + m , a[i] ) - b;
if( l == 1 ) res = max( res , b[l] - a[i] );
else if( l == m + 1 ) res = max( res , a[i] - b[m] );
else res = max( res , min( b[l] - a[i] , a[i] - b[ l - 1 ] ) );
}
cout << res << endl;
}
K 正方体
签到题目
#include <bits/stdc++.h>
using namespace std;
int a[4][6] , x , y ;
void slove()
{
for( int i = 1 ; i <= 3 ; i ++ )
{
for( int j = 1 ; j <= 4 ; j ++ ) cin >> a[i][j];
}
for( int i = 1 ; i <= 4 ; i ++ )
{
if( a[1][i] ) x = a[1][i];
if( a[3][i] ) y = a[3][i];
}
if( x != y || a[2][1] != a[2][3] || a[2][2] != a[2][4] ) cout << "No!\n";
else cout << "Yes!\n";
}
int main()
{
int t;
cin >> t;
for( int i = 1 ; i <= t ; i ++ )
{
slove();
if( i % 50 == 0 ) cout <<"\n";
}
return 0;
}
L 简单的分数
小学数学?通分再约分喽
#include <bits/stdc++.h>
using namespace std;
int gcd( int x , int y ) { return ( y ? gcd( y , x % y ) : x ); }
void slove()
{
int op , a , b , c , d ,e;
cin >> op >> a >> b >> c >> d;
a *= d , c *= b;
if( op ) a += c;
else a -= c;
b *= d;
e = gcd( a , b );
a /= e , b /= e;
if( b < 0 ) b = -b , a = -a;
cout << a <<"/" << b << endl;
}
int main()
{
int t; cin >> t;
while( t -- ) slove();
return 0;
}
M HJ浇花
差分模板
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n , a[N] , m , cnt[N] , t ;
int main()
{
cin >> n;
for( int i = 1 , l , r ; i <= n ; i ++ )
{
cin >> l >> r ;
a[l] ++ , a[ r + 1 ] -- ;
m = max( m , r );
}
for( int i = 1 ; i <= m ; i ++ ) a[i] += a[ i - 1 ];
for( int i = 0 ; i <= m ; i ++ ) cnt[ a[i] ] ++ , t = max( t , a[i] );
for( int i = 1 ; i <= n ; i ++ ) cout << cnt[i] << " ";
cout << endl;
}