A dfs
#include<bits/stdc++.h>
using namespace std;
int a[100];
int ans;
bool st[20240000];
bool check(int date){
if(st[date])return false;
int mm=date/100%100;
int dd=date%100;
if(mm>12||mm<=0)return false;
else if(mm==1||mm==3||mm==5||mm==7||mm==8||mm==10||mm==12){
if(dd>0&&dd<=31){st[date]=true;return true;}
}else if(mm==2){
if(dd>0||dd>=18){st[date]=true;return true;}
}else{
if(dd>0&&dd<=30){st[date]=true;return true;}
}
return false;
}a
void dfs(int x,int pos,int date){
//x 遍历到序列的哪个下标
// pos 8长度的子序列到哪一个序列了
//date 形成的日期
if(x==100)return;
if(pos==8){
if(check(date))ans++;
return;
}
if((pos==0&&a[x]==2)||(pos==1&&a[x]==0)||(pos==2&&a[x]==2)
||(pos==3&&a[x]==3)
||(pos==4&&a[x]>=0&&a[x]<=1)
||(pos==5&&a[x]>=0&&a[x]<=9)
||(pos==6&&a[x]>=0&&a[x]<=3)
||(pos==7&&a[x]>=0&&a[x]<=9)){
dfs(x+1,pos+1,date*10+a[x]);
}
//如果都不满足,就跳过这个数字开始下一个
dfs(x+1,pos,date);
}
int main(){
for(int i=0;i<100;i++){
cin>>a[i];
}
dfs(0,0,0);
cout<<ans<<endl;
return 0;
}
B 枚举
#include<bits/stdc++.h>
using namespace std;
const int len=23333333;
const long double xxs=11625907.5798;
const long double ee=1e-4;
int main(){
for(int i=0;i<=len/2;i++){
int u=i;
int v=len-i;
//保证它是浮点数
long double res=-1.0*u*u/len*log2(1.0*u/len)
-1.0*v*v/len*log2(1.0*v/len);
if(fabs(res-xxs)<ee){
cout<<i;
break;
}
}
return 0;
}
C 推公式
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n ; cin >> n ;
int mi = 0 , mx = 2e9 ;
for(int i = 1 ; i <= n ; i ++)
{
int a , b ; cin >> a >> b ;
int r = a/b , l = a/(b+1)+1;
mi = max(mi , l) , mx = min(mx , r) ;
}
cout << mi << ' ' << mx << endl ;
return 0;
}
D dp
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15;
struct plane{
int t,d,l;
}p[N];
int n;
bool st[N];
bool dfs(int u,int last){
if(u==n){
return true;
}
for(int i=0;i<n;i++){
if(!st[i]&&last<=p[i].t+p[i].d){
st[i]=true;
if(dfs(u+1,max(last+p[i].l,p[i].t+p[i].l)))return true;
st[i]=false;
}
}
return false;
}
int main(){
int t;cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++){
int t,d,l;cin>>t>>d>>l;
p[i].t=t;p[i].d=d;p[i].l=l;
}
memset(st,false,sizeof st);
bool res=dfs(0,0);
if(res)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
//cout<<res<<endl;
}
return 0;
}
F bfs
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=60;
int t;
int n,m;
char mp[N][N];
bool st[N][N],vst[N][N];
int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,-1,1,-1,1};
void bfs(int x,int y){
queue<PII>q;
q.push({x,y});
st[x][y]=true;
while(q.size()){
auto t=q.front();
q.pop();
int xx=t.first,yy=t.second;
for(int i=0;i<4;i++){
int a=xx+dx[i],b=yy+dy[i];
if(a>=0&&a<m&&b>=0&&b<n&&!st[a][b]&&mp[a][b]=='1'){
q.push({a,b});
st[a][b]=true;
}
}
}
// for(int i=0;i<m;i++){
// for(int j=0;j<n;j++){
// if(st[i][j])cout<<'1';
// else cout<<'0';
// //cout<<' ';
// }
// cout<<endl;
// }
// cout<<endl;
}
bool bfs_out(int x,int y){
memset(vst,false,sizeof vst);
queue<PII>q;
q.push({x,y});
vst[x][y]=true;
while(q.size()){
auto t=q.front();
q.pop();
int xx=t.first,yy=t.second;
//cout<<"xx="<<xx<<" yy="<<yy<<endl;
if(xx==0||xx==m-1||yy==0||yy==n-1){
//cout<<"xx="<<xx<<" yy="<<yy<<endl;
//cout<<"x="<<x<<" y="<<y<<endl;
return true;
}
for(int i=0;i<8;i++){
int a=xx+dx[i];
int b=yy+dy[i];
// if(a==0||a==m-1||b==0||b==n-1){
// return true;
// }
if(a>=0&&a<m&&b>=0&&b<n&&!vst[a][b]&&mp[a][b]=='0'){
q.push({a,b});
//cout<<"a="<<a<<" b="<<b<<endl;
//cout<<"a="<<xx<<"+"<<dx[i]<<" b="<<yy<<"+"<<dy[i]<<endl;
vst[a][b]=true;
}
}
}
return false;
}
/*
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
*/
int main(){
cin>>t;
while(t--){
cin>>m>>n;
for(int i=0;i<m;i++){
cin>>mp[i];
}
memset(st,false,sizeof st);
int ans=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(mp[i][j]=='1'&&!st[i][j]){
bfs(i,j);
if(bfs_out(i,j))ans++;
}
}
}
cout<<ans<<endl;
//cout<<"t="<<t<<"时 "<<ans<<endl;
}
return 0;
}
G 前缀和
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈竟然靠自己ac了
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int n;
string str;
char a,b;
int arr[N],s[N];
int main(){
cin>>n;
cin>>str>>a>>b;
int len=str.length();
for(int i=1;i<len;i++){
if(str[i]==b){
arr[i]=1;
}
s[i]=s[i-1]+arr[i];
//cout<<s[i]<<' ';
}
//cout<<endl;
long long sum=0;
for(int i=0;i<len-n+1;i++){
if(str[i]==a){
int l=i+n-1;int r=len-1;
//cout<<"s[r]="<<s[r]<<endl;
//cout<<"s[l-1]="<<s[l-1]<<endl;
//cout<<s[r]-s[l-1]<<endl;;
sum+=s[r]-s[l-1];
}
}
cout<<sum;
return 0;
}
H 链表+优先队列
#include<bits/stdc++.h>
#define ky second
#define vl first
using namespace std;
typedef long long LL;
typedef pair<LL,int>PLI;
const int N=500010;
LL n,m,a[N];
int pre[N],nxt[N];
priority_queue<PLI>q;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
q.push({-a[i],-i});//存相反数,因为每次要选取最小且靠前的值
pre[i]=i-1;
nxt[i]=i+1;
}
pre[1]=-1;
nxt[n]=-1;
while(m--){
//把无用的也就是已经被更改的数据弹出去,直到找到争取的最小的数以及
//下标为止,因为每次操作会将序列中的一些数的值发生变化,变化之后之
//前的这些数已经算是旧的数,到时候直接弹出去,只选取有用的数
PLI t;
int k,v; //键和值
do{
t=q.top();
q.pop();
k=-t.ky,v=-t.vl;
}while(a[k]!=v);
//cout<<"k="<<k<<" a[k]="<<a[k]<<" v="<<v<<endl;
int PRE=pre[k];int NXT=nxt[k];
if(PRE!=-1){
a[PRE]+=v;
q.push({-a[PRE],-PRE});//新数也放进去
nxt[PRE]=NXT;//操作这个链表
//cout<<"PRE="<<PRE<<endl;
//cout<<"A[PRE]="<<a[PRE]<<endl;
}
if(NXT!=-1){
a[NXT]+=v;
q.push({-a[NXT],-NXT});
pre[NXT]=PRE;
//cout<<"NXT="<<NXT<<endl;
//cout<<"A[NXT]="<<a[NXT]<<endl;
}
a[k]=-1;//销毁这个数
/*for(int i=1;i<=n;i++){
if(a[i]!=-1)cout<<a[i]<<' ';
}
cout<<endl;*/
}
for(int i=1;i<=n;i++){
if(a[i]!=-1)cout<<a[i]<<' ';
}
return 0;
}
I
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100010;
const int M=2*N;
int e[M],ne[M],w[M],h[N],idx;
int depth[N],f[N][20];
LL d[N];
int q[N];
int n,k;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa)
{
depth[u] = depth[fa] + 1;
f[u][0] = fa;
for (int i = 1; i <= 19; i++)
f[u][i] = f[f[u][i - 1]][i - 1];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
d[j] = d[u] + w[i];
dfs(j, u);
}
}
int lca(int a,int b){
if(depth[a]<depth[b])return lca(b, a);
for(int i=18;~i;i--){
if(depth[f[a][i]]>=depth[b])
a=f[a][i];
}
if(a==b)return a;
for(int i=18;~i;i--){
if(f[a][i]!=f[b][i])
{
a=f[a][i];
b=f[b][i];
}
}
return f[a][0];
}
LL get(int a,int b){
int p=lca(a,b);
//cout<<"p="<<p<<" d[p]="<<d[p]<<endl;
return d[a]+d[b]-2*d[p];
}
int main(){
memset(h, -1, sizeof h);
scanf("%d%d", &n, &k);
for (int i = 1; i < n; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
dfs(1, 0);
for (int i = 0; i < k; i++) scanf("%d", &q[i]);
LL sum = 0;
for (int i = 0; i + 1 < k; i++) {
//cout<<get(q[i], q[i + 1])<<endl;
sum += get(q[i], q[i + 1]);
}
//cout<<sum<<" ";
for (int i = 0; i < k; i++)
{
LL res = sum;
// 跳过i(i不是端点),等同于砍掉i-1->i和i->i+1,加上i-1->i+1
if (i && i != k - 1) res += get(q[i - 1], q[i + 1]) - get(q[i - 1], q[i]) - get(q[i], q[i + 1]);
// 跳过i(i是左端点),等同于砍掉i->i+1
else if (!i) res -= get(q[i], q[i + 1]);
// 跳过i(i是右端点),等同于砍掉i-1->i
else res -= get(q[i - 1], q[i]);
printf("%lld ", res);
}
puts("");
return 0;
/*memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=1;i<n;i++){
int u,v,t;cin>>u>>v>>t;
add(u,v,t);
add(v,u,t);
}
//depth[1]=1;depth[0]=0;
dfs(1,0);
LL sum=0;
for(int i=0;i<m;i++){
cin>>A[i];
}
for(int i=0;i<m-1;i++){
cout<<"A[i]="<<A[i]<<" A[i+1]="<<A[i+1]<<endl;
sum+=get(A[i],A[i+1]);
cout<<get(A[i],A[i+1])<<endl;
}
cout<<sum<<" ";
for(int i=0;i<m;i++){
LL res=sum;
if(i==0){
res-=get(A[i],A[i+1]);
}else if(i==m-1){
res-=get(A[i-1],A[i]);
}else{
res-=get(A[i-1],A[i])+get(A[i],A[i+1]);
res+=get(A[i-1],A[i+1]);
}
cout<<res<<" ";
}
cout<<lca(6,5);
return 0;*/
}
J
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#define ms(s,x) memset(s, x, sizeof(s))
using namespace std;
typedef pair<int,int>PII;
typedef long long LL;
const int N=200010;
map<PII,int>mp;
vector<int>e[N];
int n,m;
int root;
int ans;
int fa[N][32],depth[N];
int q[N];
int f[N];
void bfs(int root){
memset(depth,0x3f,sizeof depth);
depth[0]=0;depth[root]=1;
queue<int>q;
q.push(root);
while(q.size()){
int t=q.front();
q.pop();
for(int j:e[t]){
//fa[j][0]=t;
if(depth[j]>depth[t]+1){
depth[j]=depth[t]+1;
q.push(j);
fa[j][0]=t;
for(int k=1;k<=15;k++){
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
}
int lca(int a,int b){
if(depth[a]<depth[b])swap(a,b);
for(int k=15;k>=0;k--){
if(depth[fa[a][k]]>=depth[b]){
a=fa[a][k];
}
}
if(a==b)return a;
for(int k=15;k>=0;k--){
if(fa[a][k]!=fa[b][k]){
a=fa[a][k];
b=fa[b][k];
}
}
return fa[a][0];
}
int dfs(int u,int fa){
int res=f[u];
for(auto v:e[u]){
if(v==fa)continue;
int g=dfs(v,u);
if(g==m){
ans=max(ans,mp[{v,u}]);
}
res+=g;
}
return res;
}
int main(){
cin >> n >> m;
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
mp[ {u, v}] = mp[ {v, u}] = i + 1;
e[u].push_back(v);
e[v].push_back(u);
}
bfs(1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
int z = lca(u, v);
f[u]++;
f[v]++;
f[z] -= 2;
}
dfs(1, -1);
cout << (ans == 0 ? -1 : ans) << '\n';
return 0;
}