A.喵喵的玩偶堆
考察排序
我们直接对数组排序然后两个指针移动即可,注意是奇数的时候特判即可
void solve()
{
cin>>n;
vector<int> a(n);
for(auto&v:a) cin>>v;
sort(a.begin(),a.end());
for(int i=0,j=n-1;i<=j;i++,j--)
if(i==j) cout<<a[i]<<' ';// 奇数的特判
else cout<<a[i]<<' '<<a[j]<<' ';
cout<<endl;
return ;
}
B.不休独舞，但伤害乱搞一下
考察模拟
题目很长我们提取有效信息就是计算每一次会带来的伤害可以简单推理一下20次之内所有人的血量必然会低于50% 剩下的每一轮的伤害就是固定的我们直接一次性算出来接着向上去整就好,注意体面每一轮计算伤害的时候是向下去整的
#define int long long // 考虑整个题目都是在long long 范围之下
int t,n;
int m[M],shang[M];
int a,b,c,d;
void solve()
{
cin>>n>>a>>b>>c>>d;
m[1]=a,m[2]=b,m[3]=c,m[4]=d;
memcpy(shang,m,sizeof m);// 表示生命上限
int ans=0;
auto check = [&](){// 生命值高于生命上限的 一半
int cnt=0;
for(int i=1;i<=4;i++){
if(2*m[i]>shang[i]) cnt++;
}
return cnt;
};
auto kou = [&](double kouxue,double sh,int cnt){// 每一次的伤害 重复计算用函数
double res=0;
res=1.0*a*sh*(1.0+min(40ll,a/1000)*0.007)*(1.0+cnt/10.0);
int lastres=(int)res;
for(int i=1;i<=4;i++){
if(2*m[i]>shang[i]){
m[i]-=(int)(1.0*shang[i]*kouxue);
}
}
return lastres;
};
for(int i=1;i<=20;i++){
// 乌 start
int x1=kou(0.024,0.1073,check()); n-=x1;
// 海 start
int x2=kou(0.016,0.0582,check()); n-=x2;
// 谢
int x3=kou(0.036,0.1492,check()); n-=x3;
if(n<=0){// 死了
cout<<i<<endl;
return ;
}
}
// 还活着剩下的每一轮的伤害是一样的
ans=20;
int x1=kou(0.024,0.1073,0);
int x2=kou(0.016,0.0582,0);
int x3=kou(0.036,0.1492,0);
int x=x1+x2+x3;
ans+=(int)ceill(1.0*n/x);
cout<<ans<<endl;
return ;
}
C.我与op不共戴天
考察数论?
我们对式子进行变化第I次的贡献是
,接着对于前n次就是求和一个等差乘以一个等比,最后题目要求我们是取模同时要的是最后的结果所以我们需要对最后的式子求极限积分即可,过于繁琐不做推导最后式子就很简洁然后按照取余要求求出答案即可
int qmi(int a,int b,int p){
LL res=1;
while(b){
if(b&1) res=res*a%p;
b>>=1;
a=a*a%p;
}
return res;
}
void solve()
{
cin>>p;
int ans=qmi(10000*qmi(p,mod-2,mod)%mod,2,mod)%mod;
cout<<ans<<endl;
return ;
}
D. 高精度除法
考查大数取余
我们发现这个并不是10进制,假设这个题是10进制那么我们就同除法原理相同从前往后开始上位取余,可以自己手动模拟10032 除以 43的过程即可理解,对于n进制我们从开头之后来乘以n就行了原理同10进制一样,注意字母的转化即可在大于等于10的数会依次使用ABCDEF
void solve()
{
cin>>n;
string s; cin>>s;
int m=0,x=0;
for(int i=0;s[i];i++){
x*=n;
if(s[i]>='A' && s[i]<='F'){
x+=s[i]-'A'+10;
}
else x+=s[i]-'0';
x%=(n-1);
}
cout<<(x==0 ? "YES" : "NO")<<endl;
return ;
}
E.紧急救援
考察爆搜
我们发现数据范围很小所有可以直接暴力搜索,不过注意题目的限制条件不能回头,不能跳过人....
char s[M][M];
char op[M];
bool st[M][M];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char d[]={'R','L','D','U'};
int mx;
void dfs(int x,int y,int u,int now,int last){// 当前这个位置 表示走了多少步 表示当前救了多少人
if(x==ex and y==ey){// 表示走到了终点
for(int i=1;i<=u;i++){
cout<<op[i];
}
cout<<endl;
exit(0);// 直接终止程序
}
for(int i=0;i<4;i++){
if(last+i==1) continue; 0 1 1 0 3 4 4 3
if(last+i==5) continue;// 表示不能回头
for(int j=1;j<=mx;j++){
int a=x+j*dx[i],b=y+j*dy[i];
if(a>n || a<1 || b>m || b<1) break;// 表示越界
if(s[a][b]=='.') continue;// 表示这个点被黑暗侵袭
if(st[a][b]) continue;// 表示这个点我曾经走过
st[a][b]=true;
op[u+1]=d[i];// 这个点我走了方向是
if(s[a][b]=='o') dfs(a,b,u+1,now+1,i);// 坐标 步数 救了一个人
else if(s[a][b]=='t' and now==cnt) dfs(a,b,u+1,now,i);
st[a][b]=false;// 回溯
break;// 表示不能跳过一个人
}
}
}
void solve()
{
cin>>n>>m;
mx=max(n,m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>s[i][j];
if(s[i][j]=='s') sx=i,sy=j;
if(s[i][j]=='o') cnt++;
if(s[i][j]=='t') ex=i,ey=j;
}
st[sx][sy]=true;
dfs(sx,sy,0,0,-100);
cout<<-1<<endl;
return ;
}
F.寻光
考察思维
我们发现我们对字符串一直是从左右开始切然后交换我们发现如果把这个字符串翻倍的话那么无论怎么操作一定是这个里面的一个子串，我们发现其实左右剪切其实等价于在移动我们的左边界,所以用左边界来变化即可
void solve()
{
cin>>n>>m;
string s; cin>>s;
s+=s; s=' '+s;
LL l=1,r=n;
while(m--){
int op,x; cin>>op>>x;
if(op==1){
l+=x;
}
else{
l-=x;
}
}
l=(l%n+n)%n;
for(int i=l;i<=l+n-1;i++) cout<<s[i];
return ;
}
G.The union and intersection of Circles
考察读题
这个题看起来是一个计算几何其实是一个伪装的题目,我们简单逻辑推理之后就是两个圆的面积之和
void solve()
{
int x,y;
double r;
double res=0;
cin>>x>>y>>r;
res=r*r*3.14159265358979323846;
cin>>x>>y>>r;
res+=r*r*3.14159265358979323846;
cout<<LF(2)<<res<<endl;
return ;
}
H.Anya想看电视，不给看就学坏⌓‿⌓
考察dp求方案数
首先我们需要发现的性质就是一个数的左右加减最后对整个序列的总和是不变的,这有什么作用呢,暂时搁置
我们考虑这样的问题也就是我们如何表示状态,不难考虑到我们可以定义dp[i][j] 表示第i个数为j的方案数即可
接着我们就会发现性质带来的作用也就是如果我一直是往后累加的话那么最后一个数的大小就会是
所以我们第二个维度也就是
同时有负数我们考虑翻倍也就是
所以我们观察题目的内存没办法使用开一个
的数组,接着我们发现其实每一个状态只用到了上一个状态所以我们考虑滚动数组,也就是依照当前这个数的位置和下一个数位的奇偶性肯定不同只为开一个二维的即可,每次清空即可
int dp[2][M];// 表示第i个数为j的方案数 考虑到总和不会变也就是j的范围为 -350*350 < j < 350*350
int w[360];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
dp[0][w[2]+N]=1;//入口
for(int i=2;i<n;i++){
int now=i%2,ne=(i+1)%2;
memset(dp[ne],0,sizeof dp[ne]);
for(int j=-N+360;j<N-360;j++){ //第i个数为j // 注意防止出现负数的处理
if(!j) (dp[ne][w[i+1]+N]+=dp[now][N])%=mod;// 注意0的时候加法和减法是一样的
else{
(dp[ne][w[i+1]+j+N]+=dp[now][j+N])%=mod;
(dp[ne][w[i+1]-j+N]+=dp[now][j+N])%=mod;
}
}
}
int res=0;
for(int i=0;i<M;i++){
(res+=dp[n%2][i])%=mod;
}
cout<<res<<endl;
return ;
}
I.互评作业
考察基环树
我们发现这是一个n个点n条边的图也就是基环树接着我们发现其实我们只需要处理每一个环上的所有位置,对于一个没有入度的点一定是有贡献的然后一直把下一个点加入即可,拓扑性质,接着我们处理带有环的部分一直dfs遍历整个环即可,一个环的贡献也是1
bool st[N];
int cnt;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>A[i];
d[A[i]]++;
}
queue<int> q;
for(int i=1;i<=n;i++){
if(!d[i]){
q.push(i); // 入度 为0 表示一定要我们要搞一手
cnt++;
}
}
while(!q.empty()){
int u=q.front(); q.pop();
if(st[u]) continue;
st[u]=true;
q.push(A[u]);// 可以搞谁
}
function<void(int)> dfs = [&](int u){// 处理环
if(st[u]) return ;
st[u]=true;
dfs(A[u]);
};
for(int i=1;i<=n;i++){
if(!st[i]){
cnt++;
dfs(i);
}
}
cout<<cnt<<endl;
return ;
}
J.武林高手
考察二分+bfs 或者dp
我们发现题目要求我们至少需要多少,我们考虑这样一个问题是否具有单调性,明显的是有的也就是如果第n天可以那么第n+1一天一定也是可以的,所以我们可以二分看当前答案是否可以走到目标点,走的过程就是bfs的过程
考虑dp的话就是从当前点一直走同时维护一个最小的跳跃的值就可以动态的变化最后到达目标点即可,这里不给出代码
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
bool check(int mid){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
st[i][j]=false;
queue<PII> q;
q.push({1,1});
while(!q.empty()){
auto [x,y]=q.front(); q.pop();
if(st[x][y]) continue;
st[x][y]=true;
if(x==n && y==m) return true;
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(a<1||a>n||b<1||b>m) continue;// 越界
if(w[a][b]-w[x][y]>mid) continue;// 超过
if(st[a][b]) continue;// 被用过
q.push({a,b});
}
}
return st[n][m];
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
int l=w[1][1],r=1000000+10;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
return ;
}
K. 奖学金失踪案
考察差分和简单二进制变化
我们会发现一个满足在范围数的变化数一定是log2(n)最后答案会到1就不再变化,同时注意0也是一种情况,那么我们只需要求出每一个数的变化次数即可,我们发现这是明显的区间加,我们可以考虑使用差分来简单维护即可,然后按照题目意思输出
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>m;
while(m--){
int l,r; cin>>l>>r;
cnt[l]++,cnt[r+1]--;
}
for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for(int i=1;i<=n;i++){
int x=a[i];
int op=cnt[i];
cout<<x;
while(x>1 && op>0){
cout<<"->"<<(x+1)/2;
x=(x+1)/2;
op--;
}
cout<<endl;
}
return ;
}
京公网安备 11010502036488号