3991

Carson_cyc
straySheep.
xiaozd
Jettblue
Countt
Hangter
yao4246

Wzp.

-浪漫主义狗-

AvariceZhao

mei_24
a睿

#include <bits/stdc++.h>
#include <cstdio>
#include <string>
using namespace std;
const int N = 1000010;
int sa[N];  // 求Alice 出现的坐标标示为1 当一个Bob出现求sa[l ~ r]

int main()
{
int k;
string str;
cin >> k;
getchar();
getline(cin, str);
long long res = 0;

for (int i = 0; i < str.size(); i++) {
i = str.find("Alice", i);
if (i == string::npos)
break;
if ((i + 5 < str.size() && isalpha(str[i + 5])) || (i >= 1 && isalpha(str[i - 1]))) {
i = i + 5;
continue;
}
sa[i + 1] = true;
}

for (int i = 1; i <= str.size(); i++) {
sa[i] += sa[i - 1];
}

for (int i = 0; i < str.size(); i++) {
i = str.find("Bob", i);
if (i == string::npos)
break;

if ((i + 3 < str.size() && isalpha(str[i + 3])) || (i >= 1 && isalpha(str[i - 1]))) {
i = i + 3;
continue;
}
// A ... Bob ... A  //坐标后面要加1 s[]数组偏移了
int l = max(0, i - k - 5) + 1, r = min(i + 3 + k + 1, (int)str.size());

res += sa[r] - sa[l - 1];
}

cout << res << endl;
return 0;
}



#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010, mod = 1e9 + 9;
ll sz[N], d[N];
ll n;
int fact[N], infact[N];
int C(int a, int b)
{
return (ll)fact[a] * infact[a - b] % mod * infact[b] % mod;
}
int qmi(int a, int b)
{
ll res = 1;
while (b) {
if (b & 1)
res = res * a % mod;
a = (ll)a * a % mod;
b >>= 1;
}

return res;
}
void init()
{
fact[0] = 1;
infact[0] = 1;
for (int i = 1; i < N; i++) {
fact[i] = (ll)fact[i - 1] * i % mod;
infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2) % mod;
}
}

int dp(int i)
{
if (sz[i] <= 1)
return 1;
int l = 2 * i, r = 2 * i + 1;
// int fl = dp(l),fr = dp(r);
// cout<<i<<" "<<l<<" "<<r<<endl;
// cout<<"---"<<sz[i] - 1<<" "<<sz[l]<<" "<<fl<<" "<<fr<<endl;
// int res = (ll)C(sz[i] - 1, sz[l]) * fl % mod * fr % mod;
// cout<<i<<" "<<res<<endl;
return (ll)C(sz[i] - 1, sz[l]) * dp(l) % mod * dp(r) % mod;
}
int main()
{
cin >> n;
for (int i = n; i >= 1; i--) {
sz[i] = 1;
int l = 2 * i, r = 2 * i + 1;
if (l <= n)
sz[i] += sz[l];
if (r <= n)
sz[i] += sz[r];
}
//for(int i = 1;i <= n;i++) cout<<sz[i]<<endl;
init();  // 初始化C(a,b);
cout << dp(1) << endl;
return 0;
}



### 公式法

$$p^2+(e*d-n-2)p+n$$

$$\frac{-b + \sqrt{b^2-4\times{a}\times{c}}}{2\times{a}}$$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
int T;
cin>>T;
while(T--){
ll e,d,n;
cin>>n>>d>>e;
ll b = -(n - e*d + 2),c = n;
if(b*b < 4*c){//无解
cout<<"NO"<<endl;
}else{
ll deta = (ll)sqrt(b*b - 4*c);
ll temp = deta*deta;
if(temp == (b*b - 4*c)){
ll p = (-b + deta)/2;
ll q = n/p;
cout<<min(p,q)<<" "<<max(p,q)<<endl;
}else{
cout<<"NO"<<endl;
}

}
}
return 0;
}


### 二分

$$p + q = m$$
$$p\times{q} = m$$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
int T;
cin>>T;
while(T--){
ll e,d,n;
cin>>n>>d>>e;
ll m = n - e*d + 2;
ll l = 1,r = m >> 1;
while(l < r){
ll mid = l + r >> 1;
if(mid * (m - mid) >= n) r = mid;
else l = mid + 1;
}

if(l * (m - l) == n){
cout<<l<<" "<<m - l<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e9;
long long qmi(long long a,long long b)
{
if(a >= 10 && b >= 10) return -1;
long long res = 1;
while(b){
if(b&1) res = res*a;
if(res > N) return -1;
a = a*a;
b >>= 1;
}
if(res > N) return -1;
return res;
}
int main()
{
long long a,b;
cin>>a>>b;
cout<<qmi(a,b)<<endl;
}


### 模拟

1. 将每个数字存入一个字符串
2. 找规律填入每个数字(每次填入一个宽度)
#include <bits/stdc++.h>
#include <climits>
#include <string>
using namespace std;
const int N = 1010;
char g[N][N];
void slove(int n)
{
memset(g, 0, sizeof g);
string s = "";
int sz = 4 * n - 4;
for (int i = 1;; i++) {
if (s.size() >= sz)
break;
s += to_string(i);
}
cout << s << endl;

int cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n + i - 1; j++) {
g[i][j] = '.'; // 填入每一个'.'
}
g[i][n - i + 1] = s[cnt++];//左边的腰
}

for (int i = 2; i <= 2 * n - 1; i++) //底
g[n][i] = s[cnt++];

for (int i = n - 1, j = 2 * n - 2; i >= 2; i--, j--)
g[i][j] = s[cnt++];//右边的腰

for (int i = 1; i <= n; i++) {
printf("%s\n", g[i] + 1);
}
}
int main()
{
int n;
while (cin >> n) {
slove(n);
}
return 0;
}



#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 200010;
int h[N],ne[N],e[N],idx;
int f[N];
int n,m;
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int dp(int u,int fa)
{
f[u] = 0;
int cnt = 0,res = 0;
for(int i = h[u];i != -1;i = ne[i]){
int j = e[i];
if(j == fa) continue;
cnt++;
res = max(res,dp(j,u));
//cout<<j<<" "<<f[j]<<endl;
}
return f[u] = res + cnt;
}
int main()
{
memset(h,-1,sizeof h);
cin>>n;
for(int i = 2;i <= n;i++){
int b;
cin>>b;
}
cout<<dp(1,-1)<<endl;
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1010;
int a[N][N];
PII node[N];
unordered_map<LL,int> st;
int n,S;
int l;
LL get(int x,int y){
return (LL)x*(l+1)+y;
}
bool check(int idx)
{
int x = node[idx].first,y = node[idx].second;
for(int i = 0;i <= S;i++){
for(int j = 0;j <= S;j++){
int tx = x + i,ty = y + j;
if(tx > l || ty > l) return false;
if(st.count(get(tx,ty)) != a[i][j]) return false;
}
}
return true;
}
int main()
{
cin>>n>>l>>S;
for(int i = 0;i < n;i++){
int x,y;
cin>>x>>y;
node[i].first = x;
node[i].second = y;
st[get(x,y)] = true;
// cout << get(x,y)<<endl;
}
for(int i = S;i >= 0;i--){
for(int j = 0;j <= S;j++){
cin>>a[i][j];
}
}
int res = 0;
for(int i = 0;i < n;i++){
if(check(i)){
res++;
}
}
cout<<res;
return 0;

}



### 暴力全排列枚举

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int g[N][N];
int cnt,st[N];
int m;
int backup[N][N],res[N][N];
void check(int a[])
{
for(int i = 0,k = 0;i < 3;i++){
for(int j = 0;j < 3;j++){
if(g[i][j]) backup[i][j] = g[i][j];
else backup[i][j] = a[k++];
}
}

int s = backup[0][0] + backup[0][1] + backup[0][2];
if(s != 15) return;
s = backup[1][0] + backup[1][1] + backup[1][2];
if(s != 15) return;
s = backup[2][0] + backup[2][1] + backup[2][2];
if(s != 15) return;

s = backup[0][0] + backup[1][0] + backup[2][0];
if(s != 15) return;
s = backup[0][1] + backup[1][1] + backup[2][1];
if(s != 15) return;
s = backup[0][2] + backup[1][2] + backup[2][2];
if(s != 15) return;

s = backup[0][0] + backup[1][1] + backup[2][2];
if(s != 15) return;

s = backup[0][2] + backup[1][1] + backup[2][0];
if(s != 15) return;

cnt++;
if(cnt == 1){
for(int i = 0,k = 0;i < 3;i++){
for(int j = 0;j < 3;j++){
res[i][j] = backup[i][j];
}
}
}
return;
}
int main()
{
for(int i = 0;i < 3;i++){
for(int j = 0;j < 3;j++){
cin>>g[i][j];
if(g[i][j]) st[g[i][j]] = true;
}
}

int num[N];
for(int i = 1;i <= 9;i++){
if(!st[i])  num[m++] = i;
}

//for(int i = 0;i < m;i++) cout<<num[i]<<endl;
do{
check(num);
if(cnt >= 2){
cout<<"Too Many"<<endl;
return 0;
}
}while(next_permutation(num,num + m));

for(int i = 0;i < 3;i++){
for(int j = 0;j < 3;j++){
cout<<res[i][j]<<" ";
}
cout<<endl;
}
return 0;
}


#include <iostream>
#include <cstring>
#include <cstring>
using namespace std;
const int N = 300010;
int d[N];
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i = 1;i <= n;i++){
int t,c;
cin>>t>>c;
d[max(1,t - c + 1)]++,d[t + 1]--;
}
for(int i = 1;i < N;i++){
d[i] += d[i - 1];
}
for(int i = 0;i < m;i++){
int q;
cin>>q;
cout<<d[q + k]<<endl;
}
return 0;
}


#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 300010;
int f[N];
int n,m;
int main()
{
cin>>n>>m;
f[0] = 1;
for(int i = 0;i < n;i++){
int w;
cin>>w;
for(int j = N;j >= w;j--){
f[j] |= f[j - w];
}
}

for(int i = m;i < N;i++){
if(f[i]){
cout<<i<<endl;
return 0;
}
}
}