河南萌新联赛2024第（三）场：河南大学
Circle
画出4个圈的交叉
所以就是1 2 4 8 14，从第二个数开始，每个+2，+4，+6，....以此类推。
void solve()
{
int a[1000005]={0};
a[0]=1;
a[1]=2;
for(int i=2;i<1000005;i++)
{
a[i]=a[i-1]+2*(i-1);
}
int n; cin>>n;
while(n--)
{
int x; cin>>x;
cout<<a[x]<<" ";
}
}
keillempkill学姐の卷积
简单的模拟，但是注意细节的处理就行。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int a[25][25];
int b[25][25];
int ans[30][30];
int n,m;
int cal(int row,int line)
{
int temp=0;
for(int i=row,x=1;i<row+n,x<=n;i++,x++){
for(int j=line,y=1;j<line+n,y<=n;j++,y++)
{
temp+=a[x][y]*b[i][j];//注意这里a是放x，y而不是i，j
}
}
return temp;
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>a[i][j];
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++) cin>>b[i][j];
//外面两层循环是遍历每一个点
for(int k=1;k<=m-n+1;k++){
for(int g=1;g<=m-n+1;g++){
ans[k][g]=cal(k,g);
}
}
for(int i=1;i<=m-n+1;i++){
for(int j=1;j<=m-n+1;j++) cout<<ans[i][j]<<" ";
cout<<endl;
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
//cout<<ans;
return 0;
}
SSH
多使用map来处理对应关系，边写边理清思路，有详细注释
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
int n,m,q; cin>>m>>n>>q;//n台主机，m个密钥对，q次查询
map<string,string>key;//存公钥和私钥，左边si钥，右边公钥
for(int i=0;i<m;i++)
{
string pub,pri;
cin>>pub>>pri;
key[pri]=pub;
}
map<string,set<string> >user;//存用户和对应的密钥
map<string,set<string> >ipv4;//对应的ipv4的地址存的用户
for(int i=0;i<n;i++)
{
string ip; cin>>ip;//ip
int num;cin>>num;//有几个用户；
while(num--)
{
string name; cin>>name;//用户名
ipv4[ip].insert(name);//保存ip地址下的对应用户
int cnt ;cin>>cnt;//公钥数量
while(cnt--) {
string keyname;//公钥名称
cin>>keyname;
user[name].insert(keyname);//保存用户对应的公钥
}
}
}
//for(auto t:user["gg"]) cout<<t<<" ";
while(q--)
{
int f1=0,f2=0;
string name ;cin>>name;
string ip; cin>>ip;
string keyname;cin>>keyname;//私钥
if(ipv4[ip].find(name)!=ipv4[ip].end() ) f1=1;//用户名在对应ip的主机上
//用户拥有该私钥对应的密钥
string ans=key[keyname];
if(user[name].find(ans)!=user[name].end()) f2=1;
if(f1&&f2) cout<<"Yes";
else cout<<"No";
cout<<endl;
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
//cout<<ans;
return 0;
}
求值
这题可以有二分的解法，也可以有三分的解法，但是三分的细节处理挺多的，我不是很会。使用二分的解法思路这么走：
1.\(∣x∗A+y∗B+z∗C−W∣\)与\(x+y+z=n\)，我们可以发现\(z=n-x-y\)，那么当你把z代入的时候就会有\((a-c)*x+(b-c)*y+n*c-w\)，可以发现当我们枚举x，去二分y的时候，只要保证了\(b>c\)，那么这个等式就可以满足单调性，所以在枚举x之前，处理b和c。
2.注意这里有一个绝对值，那么我们可以把找\(∣x∗A+y∗B+z∗C−W∣\)，看成找\(x∗A+y∗B+z∗C−W>=0\)的最小值和找\(x∗A+y∗B+z∗C−W<=0\)的最大值（负数最大时，绝对值最小），都找完以后呢，再去取最小值。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int a,b,c,n,w;
int cacl(int x,int y)//计算结果
{
return (a-c)*x+(b-c)*y+n*c-w;
}
void solve()
{
cin>>a>>b>>c>>n>>w;
if(b<c) swap(b,c);//保证b>c
int ans=1e19;
for(int i=0;i<=n;i++)//枚举x，去二分y
{
//找等式大于0时的最小值
int l=0,r=n-i;
int res=-1;
while(l<=r)
{
int mid=(l+r)>>1;//mid 相当于y，i相当于x
if(cacl(i,mid)>=0) res=cacl(i,mid),r=mid-1;
else l=mid+1;
}
int one=-1;
//找等式小于0时的最大值
l=0,r=n-i;
while(l<=r)
{
int mid=(l+r)>>1;
if(cacl(i,mid)<=0){
one=-cacl(i,mid);//要的是绝对值
l=mid+1;
}
else r=mid-1;
}
if(res!=-1) ans=min(ans,res);
if(one!=-1) ans=min(ans,one);
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
累加器
这一题使用ymz的超级思路：对于每一个数从0到该数的二进制位的变化数为这个数除以每个二进制位的大小，举个例子：5，从0->5，二进制位对应为0101，那么使用到的二进制位的大小为4 2 1，所以变化次数为5/1+5/2+5/4=8次，样例1:1 4，1的变化次数为1，那么答案就是8-1=7。
总结：答案就是y+x的变化次数-y的变化次数
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int a[35];
void ycj()
{
a[0]=1;
for(int i=1;i<=32;i++) a[i]=a[i-1]*2;
}
void solve()
{
int xx,yy;cin>>xx>>yy;
yy+=xx;
int ans=0;
for(int i=0;i<=30;i++)
{
ans+=yy/a[i]-xx/a[i];
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
ycj();
int t=1;
cin>>t;
while(t--) solve();
return 0;
}