[哈理工程序竞赛]题解

哈理工

A race

签到题直接模拟，最大时间就是L/v2

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int v1,v2,t,s,L;
    cin>>v1>>v2>>t>>s>>L;
    int hong=L/v2;
    int hpos=0,mpos=0;
    for(int i=0;i<hong;){
        if(mpos-hpos>=t){
            hpos+=s*v2;
            i+=s;
        }else {
            hpos+=v2;
            mpos+=v1;
            ++i;
        }
        if(mpos>=L&&hpos<L) {cout<<"Ming "<<min(i,hong);break;}
        else if(mpos>=L&&hpos>=L) {cout<<"Tie "<<min(i,hong);break;}
        else if(mpos<L&&hpos>=L) {cout<<"Hong "<<min(i,hong);break;}
    }
    return 0;
}

B 排序

要求abs(a[i]+a[j])最小且i+j最小，那么按abs(val)直接排序，存储每个数第一次出现的index
然后扫描一遍最小值就是 $min(a[i].val + a[i - 1].val) 0<i<n$

#include <bits/stdc++.h>
using namespace std;

struct Data {
    int val, index; //存值和索引
} a[100001];

unordered_map<int, int> v;

bool flag1 = false, flag2 = false;

bool cmp(Data x, Data y) {
    if (abs(x.val) == abs(y.val)) {
        return x.index < y.index;
    }
    return abs(x.val) < abs(y.val);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].val;
        if (a[i].val > 0) flag1 = true;
        else if (a[i].val < 0) flag2 = true;
        a[i].index = i + 1;
        if (v.find(a[i].val) == v.end()) { //存储第一次出现的位置
            v[a[i].val] = i + 1;
        }
    }
    sort(a, a + n, cmp);
    if (!flag2) { // 不存在小于0的数
        cout << abs(a[0].val + a[1].val) << " " << a[0].index + a[1].index << endl;
    } else if (!flag1) {
        cout << abs(a[0].val + a[1].val) << " " << a[0].index + a[1].index << endl;
    } else {
        int mmin = 1 << 30;
        int idxSum = 0;
        for (int i = 1; i < n; i++) {
            if (abs(a[i].val + a[i - 1].val) < mmin) {
                mmin = abs(a[i].val + a[i - 1].val);
                //idxSum = a[i].index+a[i-1].index;
                idxSum = v[a[i].val] + v[a[i - 1].val];
            } else if (abs(a[i].val + a[i - 1].val) == mmin) {
                idxSum = min(idxSum, v[a[i].val] + v[a[i - 1].val]);
                //idxSum = min(idxSum,a[i].index+a[i-1].index);
            }
        }
        cout << mmin << " " << idxSum << endl;
    }
    return 0;
}

C bfs

bfs板子题

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
#define ll __int128_t
const int inf = 0x3f3f3f3f;
const int maxn = 60;
const int M = 1e9+7;
int n,m,k,ok;

char a[maxn][maxn];

bool judge(int x,int y)
{
    for(int i = -1; i <= 1; i++)
    {
        for(int j = -1; j <= 1; j++)
        {
            if(a[x+i][y+j] == '*') return true;
        }
    }
    return false;
}

struct node
{
    int x,y,z;
    node(){}
    node(int a,int b,int c) {
        x = a,y = b,z = c;
    }
};

int to[4][2] = {0,1,1,0,0,-1,-1,0};

bool vis[maxn][maxn];

int bfs(int x,int y)
{
    queue<node> q;
    q.push(node(x,y,0));
    vis[x][y] = 1;
    while(!q.empty())
    {
        x = q.front().x;
        y = q.front().y;
        int z = q.front().z;
        q.pop();
        if(judge(x,y)) continue;
        if(a[x][y] == 'S') return z;
        for(int i = 0; i < 4; i++)
        {
            int xx = x + to[i][0];
            int yy = y + to[i][1];
            if(xx <= 0 || yy <= 0 || xx > n || yy > m) continue;
            if(judge(xx,yy) || vis[xx][yy]) continue;
            vis[xx][yy] = 1;
            q.push(node(xx,yy,z+1));
        }
    }
    return -1;
}


signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        cin>>(a[i]+1);
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(a[i][j] == 'E')
            {  
                int ans = bfs(i,j);
                if(ans == -1)
                {
                    puts("Impossible");
                }
                else
                {
                    cout<<ans<<endl;
                }

            }
        }
    }
    return 0;
}

K 快速幂逆元

因为是最短路，所以只能往右或者往下走，从(1,1)走到(x,y)点选x-1步下 y-1步右
所以答案为C(x-1+y-1,x-1),因为数很大所以利用逆元（快速幂求法）

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAN = 2e6 + 1;
const ll MOD = 1e9+7;
const ll p = 1e9+7;
// ax=1(mod b) 费马小定理ax=a^b-1(mod b)  x=a^b-2(mod b)
ll qpow(long long a, long long b)
{
    ll ans = 1;
    //a = (a % p + p) % p;
    while(b) {
        if (b & 1) ans = (a * ans) % p;
        a = (a * a) % p;
        b>>=1;
    }
    return ans;
}
ll ff[MAN];
ll rff[MAN]; // n!的逆元
ll Combination(ll x,ll y){
    return (ff[x]*rff[x-y]%MOD)*rff[y]%MOD;
}

int main(){
    int t;cin>>t;
    ff[0]=1;rff[0]=1;
    for(int i=1; i<=MAN; i++) {//预计算n!
        ff[i]=(ff[i-1]*i)%MOD;
        rff[i]=qpow(ff[i],MOD-2);
    }
    while(t--){
        ll x,y;cin>>x>>y;
        cout<<Combination(x-1+y-1,x-1)<<endl;
    }
    return 0;
}

G：XoR

找出最大值N的最高位，然后所有位都变为1就是最大值（可以试一下，总能凑出来）

//找出最大值N的最高位，然后所有位都变为1就是最大值
#include<bits/stdc++.h>
#define N 100005
using namespace std;

int main()
{
    long long n;cin>>n;
    if(n==1) cout<<0;
    else{
        int num=0;
        while(n){
            num++;
            n>>=1;
        }
        cout<<(long long)((1LL<<num)-1);
    }
    return 0;
}

H maze

dfs,从某个点能到多少个点，想象成一个并查集，集合里面所有点能到的点的数目都是集合内点的总数。

#include <bits/stdc++.h>
using namespace std;
int n, m, q;
char maze[3005][3005];
typedef pair<int, int> P;
queue<P> que;
int vis[3005][3005];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int pointTol = 0;

bool judge(int x, int y) {
    if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y]) {
        return true;
    }
    return false;
}

void dfs(int x, int y) {
    int tx, ty;
    for (int i = 0; i < 4; i++) {
        tx = x + dx[i], ty = y + dy[i];
        if (judge(tx, ty) && maze[x][y] != maze[tx][ty]) {
            pointTol++;
            vis[tx][ty] = 1;
            que.push({tx, ty});
            dfs(tx, ty);
        }
    }
    return ;
}

int main() {
    cin >> n >> m >> q;
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!vis[i][j]) {
                que.push({i, j});
                vis[i][j] = 1;
                pointTol = 1;
                dfs(i, j);
                while (!que.empty()) {
                    vis[que.front().first][que.front().second] = pointTol;
                    que.pop();
                }
            }
        }
    }
    int x, y;
    while (q--) {
        cin >> x >> y;
        cout << vis[x - 1][y - 1] << endl;
    }
    return 0;
}

D

难题，异或和为x，和为y；求选出的数组最小个数
选几个例子可以推到x<=y 且x和y的奇偶性相同；
如果x=y显然只需要一个数就可以了
如果 $x<y$ 要知道有个性质就是若x&a==0,则(x+a)^a=x^a^a=x
如果 $a=(y-x)/2$ 是不是只需要两个数(x,x+a) 如果不满足x&a=0，就只能是(x,a,a)三个数

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x,y;
    while(~scanf("%d %d",&x,&y)){
        if(x==0&&y==0) {
            cout<<0;
        }
        else if((x&1) != (y&1)) cout <<-1;
        else if(x==y) cout<<1;
        else if(x>y){
            cout<<-1;
        }else{
            int a=(y-x)/2;
            if((x&a)==0) cout<<2;
            else cout<<3;
        }
        cout<<endl;
    }
}

L

签到题排序，枚举每个数a[i] 二分找到第一个大于等于a[i]+5的位置即可

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+2;
ll a[N];
int main(){
    int n;cin>>n;
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    sort(a,a+n);
    ll ans=0;
    for(int i=0;i<n;++i){
        ll x=upper_bound(a,a+n,a[i]+5)-a-i;
        ans=max(ans,x);
    }
    cout<<ans;
    return 0;
}

J

签到题，直接字符串比较大小即可

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s1,s2;
    cin>>s1>>s2;
    if(s1.size()>s2.size()){
        cout<<">";return 0;
    }else if(s1.size()<s2.size()){
        cout<<"<";return 0;
    }
    if(s1.compare(s2)==0){
        cout<<"=";
    }else if(s1.compare(s2)>0){
        cout<<">";
    }else{
        cout<<"<";
    }
    return 0;
}