[哈理工程序竞赛]题解
哈理工
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
然后扫描一遍 最小值就是
#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&a==0,则(x+a)^a=x^a^a=x
如果 是不是只需要两个数(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;
} 
