P9754 [CSP-S 2023] 结构体
一年的痛终于解决。
一个结构体的对齐要求为其成员的对齐要求的 \(\gcd\)，其大小为大于等于实际大小的最小整除对齐要求的数，基础类型的对齐要求为其大小。
给你一个无限长的内存，头地址为 \(0\)，支持以下操作：
X k t1 n1...tk nk声明一个结构体名字为 \(X\) 包含 \(k\) 个成员，第 \(i\) 个成员的类型为 \(t_i\)，名字为 \(n_i\)。输出结构体大小和对齐要求；t n定义一个变量名字为 \(n\)，类型为 \(t\)。输出其开始地址；s求变量 \(s\) 的开始地址；addr求包含地址 \(addr\) 的变量名（精确到基础类型层面）。
按 要 求 模 拟 即 可，时间复杂度 \(O(可过)\)。3、4 操作莫名有种求排名、第 \(k\) 小的感觉？
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int maxaddress;
const int maxn=203;
int num; // 类型数
struct info{
int type;
string name;
int pos; // 起始位置
bool operator<(const info &o)const{
return pos<o.pos;
}
};
struct node{
vector<info>pb; // 包含的类型编号
int byd; // 使用字节数
int lim; // 对齐要求
map<string,int>t;// 成员名转编号
}type[maxn];
map<string,int>mp; // 类型名转编号
map<string,int>gp; // 变量名转编号
int n;
void def_struct(string s,int k){
string t,r;
mp[s]=++num;
for(int i=1;i<=k;i++){
cin>>t>>r;
int ty=mp[t];
node now=type[ty];
int lastpos=((type[num].byd-1)/now.lim+1)*now.lim;
if(i==1) lastpos=0;
type[num].t[r]=i-1;
type[num].pb.push_back({ty,r,lastpos});
type[num].lim=max(type[num].lim,type[ty].lim);
type[num].byd=lastpos+now.byd;
}
type[num].byd=((type[num].byd-1)/type[num].lim+1)*type[num].lim;
cout<<type[num].byd<<' '<<type[num].lim<<'\n';
}
int cnt;
info memory[maxn]; // 内存中的变量
void def_var(string t,string r){
node now=type[mp[t]];
int lastpos=((maxaddress-1)/now.lim+1)*now.lim;
if(!cnt) lastpos=0;
gp[r]=++cnt;
memory[cnt]={mp[t],r,lastpos};
maxaddress=lastpos+now.byd;
cout<<lastpos<<'\n';
}
int find_pos(string s,int x){
return type[x].pb[type[x].t[s]].pos;
}
int find_pot(int s,int x){
return type[x].pb[s].pos+type[type[x].pb[s].type].byd;
}
int dfs1(string s,int fa){
int pos=s.find(".");
if(pos==EOF){
return find_pos(s,fa);
}
string tmp=s.substr(0,pos);
return find_pos(tmp,fa)+dfs1(s.substr(pos+1),type[fa].pb[type[fa].t[tmp]].type);
}
string S;
void dfs2(int now,int fa){
if(fa<=4) return;
int pos=upper_bound(type[fa].pb.begin(),type[fa].pb.end(),(info){0,"",now})-type[fa].pb.begin()-1;
if(now<find_pot(pos,fa)){
S+='.';
S+=type[fa].pb[pos].name;
dfs2(now-type[fa].pb[pos].pos,type[fa].pb[pos].type);
}else{
S="ERR";
}
}
signed main(){
type[++num].byd=1;
type[num].lim=1;// byte
mp["byte"]=num;
type[num].pb.push_back({0,"",0});
type[++num].byd=2;
type[num].lim=2;// short
mp["short"]=num;
type[num].pb.push_back({0,"",0});
type[++num].byd=4;
type[num].lim=4;// int
mp["int"]=num;
type[num].pb.push_back({0,"",0});
type[++num].byd=8;
type[num].lim=8;// long
mp["long"]=num;
type[num].pb.push_back({0,"",0});
cin>>n;
while(n--){
int opt,k,addr;
string s,t,r;
cin>>opt;
if(opt==1){
cin>>s>>k;
def_struct(s,k);
}else if(opt==2){
cin>>t>>r;
def_var(t,r);
}else if(opt==3){
cin>>s;
int pos=s.find(".");
if(pos==EOF){
cout<<memory[gp[s]].pos<<'\n';
continue;
}
string tmp=s.substr(0,pos);
cout<<memory[gp[tmp]].pos+dfs1(s.substr(pos+1),memory[gp[tmp]].type)<<'\n';
}else{
S.clear();
cin>>addr;
int pos=upper_bound(memory+1,memory+cnt+1,(info){0,"",addr})-memory-1;
if(addr<memory[pos].pos+type[memory[pos].type].byd){
S=memory[pos].name;
dfs2(addr-memory[pos].pos,memory[pos].type);
}else{
S="ERR";
}
cout<<S<<'\n';
}
}
return 0;
}
P9118 [春季测试 2023] 幂次
给出 \(n,k\)，\(S=\{x\in [1,n]\mid x=t^w,t\in[1,n],w\ge k\}\)，求 \(|S|\)。
\(n\le 10^{18},k\le 100\)
\(k=1\) 直接输出 \(n\)，\(k\ge 3\) 时，\(t\) 最大 \(\sqrt[k]{n}=10^6\)，不会 T。
当 \(k=2\) 时，考虑容斥。先把所有完全平方数加上，再加上其他的，注意判重，当且仅当 \(2\nmid w\) 时有贡献，时间复杂度为 \(O(\sqrt[3]{n})\)。
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e6+3;
const int maxv=1e6;
const int maxp=1e9;
int n,cnt,C,k;
int pr[maxn];
bool isp[maxn];
signed main(){
ios::sync_with_stdio(0);
cin>>n>>k;
int base=0;
for(int i=2;i<=maxv;i++){
__int128 now=i;base=1;
if(isp[now]) continue;
while(1){
base++;
now=now*i;
if(base>=k&&now<=n){
if(now<=n&&base%k==0){
if(now<=maxv) isp[now]=1;
continue;
}
cnt++;
}
if(now<=maxv) isp[now]=1;
if(now>=n) break;
}
}
cnt+=powl(n,1.0/k)-1;
cout<<cnt+1;
return 0;
}
双倍经验：[ABC361F] x = a^b
标签：addr,int,lim,num,trichlorotrifluoroethane,byd,type From： https://www.cnblogs.com/DEV3937/p/18447239/trichlorotrifluoroethane