密码锁
#include<bits/stdc++.h> using namespace std; const int N=11,mod=10; int n,ans,dp[N][N][N][N][N]; int main() { cin>>n; for(int i=1;i<=n;i++) { int a,b,c,d,e; cin>>a>>b>>c>>d>>e; for(int j=1;j<=9;j++) { dp[(a+j)%mod][b][c][d][e]++; dp[a][(b+j)%mod][c][d][e]++; dp[a][b][(c+j)%mod][d][e]++; dp[a][b][c][(d+j)%mod][e]++; dp[a][b][c][d][(e+j)%mod]++; dp[(a+j)%mod][(b+j)%mod][c][d][e]++; dp[a][(b+j)%mod][(c+j)%mod][d][e]++; dp[a][b][(c+j)%mod][(d+j)%mod][e]++; dp[a][b][c][(d+j)%mod][(e+j)%mod]++; } } for(int i=0;i<=9;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) for(int u=0;u<=9;u++) for(int v=0;v<=9;v++) if(dp[i][j][k][u][v]==n)ans++; cout<<ans; return 0; }消消乐
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=2e6+5; int n,dp[N],a[N][26],to[N]; char s[N]; ll ans; int main() { scanf("%d%s",&n,s+1); for(int i=1;i<=n;i++) { to[i]=i; int x=a[to[i-1]][s[i]-'a']; if(x) to[i]=to[x-1],dp[i]=dp[x-1]+1; a[to[i]][s[i]-'a']=i,ans+=dp[i]; } printf("%lld\n",ans); return 0; }结构体
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pr; const int MAXN=256; ll max(ll x,ll y){return x>y?x:y;} ll min(ll x,ll y){return x<y?x:y;} pr mp(ll x,ll y){return (pr){x,y};} //用来输入的变量 ll n,op,k,addr_in; string s,ti,ni,in1[MAXN],in2[MAXN]; //类型结构体 struct Type{ string Name;//类型名称 vector<Type*> Member_Type;//类型成员类型 vector<string> Member_Name;//类型成员元素 ll Memory_Size;//类型占用内存大小 ll Memory_Align;//类型对齐要求 void clear(){ Name.clear(); Member_Type.clear(); Member_Name.clear(); Memory_Align=Memory_Size=0; } }; Type Def_Type[MAXN];//已被定义过的类型 ll Type_Num;//已被定义过的类型数量 map<string,Type*> Name_To_Type;//名称到类型的映射 //元素结构体 struct Element{ Type Ele_Type;//元素类型 string Name;//元素名称 ll Address;//元素起始地址 void clear(){ Ele_Type.clear(); Name.clear(); Address=0; } }; Element Def_Ele[MAXN];//已被定义过的元素 ll Ele_Num;//已被定义过的元素数量 map<string,Element*> Name_To_Ele;//名称到元素的映射 //地址 ll Addr_Pos;//已分配到的地址位置 map<pr,Element*> Addr_To_Ele;//地址到元素的映射 //函数 void Nothing();//一个不知道干什么用也没有存在感的空函数 void init();//预处理 void Type_Create(string,ll,string*,string*);//创建一个类型的函数 void Ele_Create(string,string);//创建一个元素的函数 ll Visit_Ele(string);//访问某个元素的函数 string Visit_Addr(ll);//访问某个地址的元素 void work();//工作 //主函数 int main(){ init(); work(); return 0; } //创建一个类型的函数 void Type_Create(string type_name,ll num,string *ar1,string *ar2){ Type New_Type;//创建一个新类型 New_Type.clear(); New_Type.Name=type_name;//名字直接赋值 for(int i=1;i<=num;i++){ New_Type.Member_Type.push_back(Name_To_Type[ar1[i]]);//成员类型直接赋值 New_Type.Member_Name.push_back(ar2[i]);//成员名称直接赋值 } ll pos=0;//起始地址默认为 0 vector<Type*>::iterator it=New_Type.Member_Type.begin(); for(;it!=New_Type.Member_Type.end();it++){//遍历成员 ll Align=(*it)->Memory_Align;//成员对齐要求 ll Size=(*it)->Memory_Size;//成员大小 New_Type.Memory_Align=max(New_Type.Memory_Align,Align);//类型的对齐要求为其成员中的最大对齐要求 if(pos%Align)pos=(pos/Align+1)*Align;//如果起始地址不满足对齐规则 pos+=Size;//下一个成员的起始地址(这个成员的终止地址) } if(pos%New_Type.Memory_Align) pos=(pos/New_Type.Memory_Align+1)*New_Type.Memory_Align;//如果终止地址不满足对齐规则 New_Type.Memory_Size=pos;//终止地址减去起始地址即为大小(起始地址默认为 0) Def_Type[++Type_Num]=New_Type;//别忘了维护这个数组 Name_To_Type[type_name]=&Def_Type[Type_Num];//别忘了维护这个映射 } //创建一个元素的函数 void Ele_Create(string type_name,string ele_name){ Element New_Ele;//创建一个新元素 New_Ele.clear(); ll Align=Name_To_Type[type_name]->Memory_Align;//该元素的类型的对齐要求 ll Size=Name_To_Type[type_name]->Memory_Size;//该元素的大小 if(Addr_Pos%Align)Addr_Pos=((Addr_Pos/Align+1)*Align);//若起始位置不满足对齐规则 New_Ele.Address=Addr_Pos;//起始地址赋值 New_Ele.Ele_Type=*Name_To_Type[type_name];//通过映射找到该类型,赋值 New_Ele.Name=ele_name;//名称直接赋值 Def_Ele[++Ele_Num]=New_Ele;//别忘了维护这个数组 Name_To_Ele[ele_name]=&Def_Ele[Ele_Num];//别忘了维护这个映射 Addr_To_Ele[mp(Addr_Pos,Addr_Pos+Size-1)]=&Def_Ele[Ele_Num];//将元素的起始位置和终止位置作为键值加入元素 Addr_Pos+=Size;//更新最高位地址 } //访问某个元素的函数 ll Visit_Ele(string ele_name){ queue<string> name;//存储名称的队列 string tool;//如其名 tool.clear(); for(int i=0;i<(ll)ele_name.length();i++){//处理名称 if(ele_name[i]=='.'){//如果遇上了调用符 name.push(tool); tool.clear(); } else tool+=ele_name[i]; } name.push(tool); ll pos=Name_To_Ele[name.front()]->Address;//起始地址为最外层元素的起始地址 Type type=Name_To_Ele[name.front()]->Ele_Type;//最外层元素的类型 name.pop(); while(!name.empty()){ string Name=name.front();//取出队首 name.pop(); vector<string>::iterator it1=type.Member_Name.begin();//遍历成员名称 vector<Type*>::iterator it2=type.Member_Type.begin();//遍历成员类型 for(;it1!=type.Member_Name.end();it1++,it2++){ if(pos%(*it2)->Memory_Align) pos=(pos/(*it2)->Memory_Align+1)*(*it2)->Memory_Align;//如果起始地址不满足对齐规则 if(*it1==Name){//如果找到了新队首 type=**it2; break; } else pos+=(*it2)->Memory_Size;//更新起始地址 } } return pos; } //访问某个地址的元素 string Visit_Addr(ll addr){ if(addr>=Addr_Pos)return "ERR";//判断地址是否在某个元素中 Element ele; map<pr,Element*>::iterator it=Addr_To_Ele.begin(); for(;it!=Addr_To_Ele.end();it++){//寻找地址所处的元素 if(addr<(*it).first.first or addr>(*it).first.second)continue; ele=*((*it).second); break; } ll pos_goal=addr-ele.Address,pos_s=0,pos_t;//目标地址、起始地址、终止地址 Type type=ele.Ele_Type;//当前元素类型 string ele_name;//元素名称 ele_name.clear(); ele_name+=ele.Name;//元素名称先加上最外层元素名称 while(!type.Member_Name.empty()){//循环直到元素类型为基本类型(此时元素类型没有成员) vector<Type*>::iterator it1=type.Member_Type.begin();//遍历当前元素类型的成员类型 vector<string>::iterator it2=type.Member_Name.begin();//遍历当前元素类型的成员名称 for(;it1!=type.Member_Type.end();it1++,it2++){ pos_t=pos_s+(*it1)->Memory_Size;//更新终止地址 if(pos_goal<pos_t and pos_goal>=pos_s){//如果目标地址在此成员中 ele_name+='.'+*it2;//更新元素名称 type=**it1;//更新元素类型 //这两行代码需要注意：不可调换位置 //因为 it2 是 type 的迭代器,type 更改后,it2 也会相应改变 //因此需要在改变 type 之前调用 it2 break; } else{//如果目标地址不在此成员中 if(it1+1==type.Member_Type.end())return "ERR";//如果这个成员是最后一个成员了,说明目标地址为空洞 ll Align=(*(it1+1))->Memory_Align;//该成员的对齐要求 if(pos_t%Align)pos_t=(pos_t/Align+1)*Align;//如果终止地址不满足对齐规则 if(pos_goal<pos_t)return "ERR";//如果目标地址在满足对齐规则后处于此成员内了,那么说明目标地址为空洞 pos_s=pos_t;//更新起始位置 } } } if(ele_name=="")return "ERR";//特判,若名称为空,则说明不存在元素包含这个地址 return ele_name; } //预处理 void init(){ Def_Type[1].Name="byte"; Def_Type[2].Name="short"; Def_Type[3].Name="int"; Def_Type[4].Name="long"; Def_Type[1].Memory_Align=Def_Type[1].Memory_Size=1; Def_Type[2].Memory_Align=Def_Type[2].Memory_Size=2; Def_Type[3].Memory_Align=Def_Type[3].Memory_Size=4; Def_Type[4].Memory_Align=Def_Type[4].Memory_Size=8; Name_To_Type["byte"]=&Def_Type[1]; Name_To_Type["short"]=&Def_Type[2]; Name_To_Type["int"]=&Def_Type[3]; Name_To_Type["long"]=&Def_Type[4]; Type_Num=4; } //工作 void work(){ scanf("%lld",&n);//输入 n while(n--){ scanf("%lld",&op);//输入操作类型 if(op==1){//操作 1 cin>>s>>k; for(int i=1;i<=k;i++)cin>>in1[i]>>in2[i]; Type_Create(s,k,in1,in2); cout<<Def_Type[Type_Num].Memory_Size<<" "<<Def_Type[Type_Num].Memory_Align<<"\n"; } else if(op==2){//操作 2 cin>>ti>>ni; Ele_Create(ti,ni); cout<<Def_Ele[Ele_Num].Address<<"\n"; } else if(op==3){//操作 3 cin>>s; cout<<Visit_Ele(s)<<"\n"; } else if(op==4){//操作 4 cin>>addr_in; cout<<Visit_Addr(addr_in)<<"\n"; } } }种树
#include<bits/stdc++.h> using namespace std; #define ___ __int128 const int N=1e5+10; int n,b[N],c[N],p[N],t[N],fa[N],stk[N]; int h[N],e[N<<1],ne[N<<1],idx; bool vis[N]; long long a[N]; inline void add(int a,int b) { e[idx]=b;ne[idx]=h[a];h[a]=idx++; } inline void dfs(int u,int p){fa[u]=p;for(int i=h[u];~i;i=ne[i]) if(e[i]!=p) dfs(e[i],u);} inline ___ calc(int x,___ l,___ r) { if(c[x]>=0) return (r-l+1)*b[x]+(r-l+1)*(l+r)/2*c[x]; ___ T=(1-b[x])/c[x]; if(T<l) return r-l+1; if(T>r) return (r-l+1)*b[x]+(r-l+1)*(l+r)/2*c[x]; return (T-l+1)*b[x]+(T-l+1)*(l+T)/2*c[x]+r-T; } inline bool check(int r) { for(int i=1;i<=n;i++) { if(calc(i,1,r)<a[i]) return false; int dl=1,dr=n; while(dl<dr) { int mid=(dl+dr+1)>>1; if(calc(i,mid,r)>=a[i]) dl=mid; else dr=mid-1; } p[i]=i;t[i]=dl;vis[i]=false; } sort(p+1,p+n+1,[](int A,int B){return t[A]<t[B];}); for(int i=1,x=0;i<=n;i++) { int now=p[i],top=0; while(!vis[now]) vis[stk[++top]=now]=true,now=fa[now]; while(top) if(t[stk[top--]]<++x) return false; } return true; } int main() { memset(h,-1,sizeof h); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%d%d",&a[i],&b[i],&c[i]); for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v);add(v,u); } dfs(1,0);vis[0]=true; int l=n,r=1e9; while(l<r) { int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } printf("%d",l); return 0; }
