wanglexi
2024-12-08 15:43:36
自己体会：
#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
using namespace std;
int t,n,to1[100005],to2[100005],end1[100005],end2[100005],sum1[100005],sum2[100005],cnt1,cnt2,ans;
string s1,s2,t1,t2;
int len(int l,int r){
return r-l+1;
}
int get10(int i){
if(to1[i]==0){
if(s1[i]=='0')return 1;
else return 0;
}
if(sum1[to1[i]]==len(i,end1[to1[i]]))return 0;
else return 1;
}
int get11(int i){
if(to1[i]==0){
if(s1[i]=='1')return 1;
else return 0;
}
if(sum1[to1[i]]==0)return 0;
else return 1;
}
int get20(int i){
if(to2[i]==0){
if(s2[i]=='0')return 1;
else return 0;
}
if(sum2[to2[i]]==len(i,end2[to2[i]]))return 0;
else return 1;
}
void output(int i){
cout<<"case "<<i<<":\n";
cout<<cnt1<<" "<<"1:\n";
for(int i=1;i<=n;i++)cout<<to1[i]<<" "<<end1[i]<<" "<<sum1[i]<<"\n";
cout<<cnt2<<" "<<"2:\n";
for(int i=1;i<=n;i++)cout<<to2[i]<<" "<<end2[i]<<" "<<sum2[i]<<"\n";
cout<<"\n";
}
int get21(int i){
if(to2[i]==0){
if(s2[i]=='1')return 1;
else return 0;
}
if(sum2[to2[i]]==0)return 0;
else return 1;
}
void solve(){
cin>>n>>s1>>s2>>t1>>t2;
s1=" "+s1,s2=" "+s2,t1="0"+t1,t2="0"+t2;
cnt1=cnt2=0;
memset(sum1,0,sizeof sum1);
memset(sum2,0,sizeof sum2);
for(int i=1;i<=n;++i){
if(t1[i-1]=='0'&&t1[i]=='1')to1[i]=++cnt1;
else if(t1[i-1]=='1'&&t1[i]=='1')to1[i]=cnt1;
else to1[i]=0;
if(t2[i-1]=='0'&&t2[i]=='1')to2[i]=++cnt2;
else if(t2[i-1]=='1'&&t2[i]=='1')to2[i]=cnt2;
else to2[i]=0;
sum1[to1[i]]+=s1[i]-'0';
sum2[to2[i]]+=s2[i]-'0';
end1[to1[i]]=i;
end2[to2[i]]=i;
}
/*
cout<<cnt1<<" "<<"1:\n";
for(int i=1;i<=n;i++)cout<<to1[i]<<" "<<end1[i]<<" "<<sum1[i]<<"\n";
cout<<cnt2<<" "<<"2:\n";
for(int i=1;i<=n;i++)cout<<to2[i]<<" "<<end2[i]<<" "<<sum2[i]<<"\n";
*/
ans=0;
for(int i=1;i<=n;i++){
int h10=get10(i);
int h11=get11(i);
int h20=get20(i);
int h21=get21(i);
// cout<<i<<": h10="<<h10<<" h11="<<h11<<" h20="<<h20<<" h21="<<h21<<"\n";
if(h10==1&&h20==1){
ans++;/*
sum1[to1[i]]--;
sum2[to2[i]]--;*/
}
else if(h11==1&&h21==1){
ans++;
sum1[to1[i]]--;
sum2[to2[i]]--;
}
else{
//cout<<i<<" ";
if(h10==0)sum1[to1[i]]--;
if(h20==0)sum2[to2[i]]--;
}
//output(i);
}
cout<<ans<<"\n";
}
int main(){
freopen("edit.in","r",stdin);
freopen("edit.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
solve();
}
return 0;
}#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
#define mod (1000000007ll)
using namespace std;
int t,n,m;
ll v,ans;
struct node{int c,d;}a[100005];
bool operator<(node x,node y){
return x.c<y.c;
}
ll qpow(ll p,ll q){
ll res=1;
while(q){
if(q&1)(res*=p)%=mod;
q>>=1,p=p*p%mod;
}
return res;
}
ll get_mod(ll p){
return (p%mod+mod)%mod;
}
void solve(){
cin>>n>>m>>v;
for(int i=1;i<=m;i++)cin>>a[i].c>>a[i].d;
sort(a+1,a+m+1);
for(int i=2;i<=m;i++)
if(a[i-1].c==a[i].c&&a[i-1].d!=a[i].d){
cout<<0<<"\n";
return;
}
ans=qpow(v*v%mod,n-a[m].c+a[1].c-1)%mod;
for(int i=2;i<=m;i++){
ll d=a[i].c-a[i-1].c;
if(d!=0)(ans*=get_mod(qpow(v,d+d)-qpow(v,d)+qpow(v,d-1)))%=mod;
}
cout<<ans<<"\n";
}
int main(){
freopen("assign.in","r",stdin);
freopen("assign.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
solve();
}
return 0;
}
//1~2 1 *#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
#define mod (1000000007ll)
using namespace std;
int c,t,a[100005],vis[100005],hav[100005],cnt,ans,cntdian;
vector<int>e1[100005],e2[100005],e3[100005];
ll n,k;
ll fac(ll x){
ll res=1;
for(ll i=1;i<=x;i++)(res*=i)%=mod;
return res;
}
ll get_mod(ll p){
return (p%mod+mod)%mod;
}
void dfs(int x,int fr,int now,int lst){
if(cntdian==n-1){
hav[now-lst]=1;
//cout<<"got "<<now-lst<<"\n";
return;
}
//int flag=0;
//cout<<x<<"\n";
for(int i=0;i<e2[x].size();i++){
int y=e2[x][i],z=e3[x][i];
//cout<<x<<"->"<<y<<" "<<z<<"\n";
if(y==fr)continue;
if(vis[y]==0){
vis[y]=1;
cntdian++;
dfs(y,x,now+(1<<z),1<<z);
vis[y]=0;
cntdian--;
}
}/*
if(!flag){
if(fr[x]==0){
return;
}
else{
dfs(fr[x],now);
}
}*/
}
void solve(){
cin>>n>>k;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
e1[u].pb(i);e1[v].pb(i);
}
for(int i=1;i<=k;i++)cin>>a[i];
if(c==18){
cout<<1<<"\n";
return;
}
if(19<=c&&c<=21){
cout<<n<<" "<<k<<" "<<get_mod(fac(n-1)*k%mod-k*(k-1)/2*fac(n-2)%mod)<<"\n";
return;
}
for(int i=1;i<=n;i++){
for(auto l:e1[i])for(auto r:e1[i])
if(l<r){
e2[l].pb(r);
e3[l].pb(++cnt);
e2[r].pb(l);
e3[r].pb(cnt);
}
}
for(int i=1;i<=k;i++){
dfs(a[i],0,0,0);
}
for(int i=1;i<=1000;i++)ans+=hav[i];
cout<<ans<<"\n";
}
int main(){
freopen("traverse.in","r",stdin);
freopen("traverse.out","w",stdout);
//ios::sync_with_stdio(0);
//cin.tie(0);cout.tie(0);
cin>>c>>t;
while(t--){
solve();
}
return 0;
}
//1~2 1 *#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
#define mod (1000000007ll)
using namespace std;
int n,q,a,st[25][500005],dep[500005],fa[500005][25];
vector<int>v[500005];
void dfs(int x,int fr){
dep[x]=dep[fr]+1;
fa[x][0]=fr;
for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(auto y:v[x]){
if(y==fr)continue;
dfs(y,x);
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int get(int l,int r){
int len=log2(r-l+1);
//cout<<l<<","<<r<<":lca("<<st[len][l]<<","<<st[len][r-(1<<len)+1]<<")="<<st[len][r-(1<<len)+1]<<"\n";
return lca(st[len][l],st[len][r-(1<<len)+1]);
}
int main(){
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
v[x].pb(y),v[y].pb(x);
//cout<<x<<"<->"<<y<<"\n";
}
dfs(1,0);
/*cin>>q;
while(q--){
int x,y;cin>>x>>y;
cout<<lca(x,y)<<"\n";
}*/
/*cout<<2<<":";
for(auto x:v[2])cout<<x<<" ";
cout<<"\n";
cout<<"son:\n";
for(int i=1;i<=n;i++)cout<<son[i]<<" ";
cout<<"\n";
cout<<"dep:\n";
for(int i=1;i<=n;i++)cout<<dep[i]<<" ";
cout<<"\n";
cout<<"top:\n";
for(int i=1;i<=n;i++)cout<<top[i]<<" ";
cout<<"\n";
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)cout<<i<<","<<j<<" "<<lca(i,j)<<"\n";*/
for(int j=1;j<=n;j++)st[0][j]=j;
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[i][j]=lca(st[i-1][j],st[i-1][j+(1<<i-1)]);
}
}
cin>>q;
while(q--){
int l,r,k,ans=0;
cin>>l>>r>>k;
for(int i=l;i+k-1<=r;i++)ans=max(ans,dep[get(i,i+k-1)]);
cout<<ans<<"\n";
}
return 0;
}
//1~2 1 *
/*
游记资料
1 第一题：编辑字符串 2024-11-30 09:16:34 2.805KB
2 第二题：遗失的赋值 2024-11-30 09:55:01 1.088KB
3 第三题：树的遍历 2024-11-30 10:40:45 875B
4 第四题：树上查询 2024-11-30 11:41:52 2.006KB
*/from 程序回收系统：
游记资料
1 第一题：编辑字符串 2024-11-30 09:16:34 2.805KB
2 第二题：遗失的赋值 2024-11-30 09:55:01 1.088KB
3 第三题：树的遍历 2024-11-30 10:40:45 875B
4 第四题：树上查询 2024-11-30 11:41:52 2.006KB100+100+4+32
BJ
初中体验