B. 序列的与和(二进制搜索)
输入
3 6
2 4 1
输出
0
说明
对于样例,其子序列有:
[2]:其与和为10(二进制),仅包含一个1,不为6,所以对答案贡献为零
[2,4]:与和为 0 ,同理,贡献为零。
[2,1]:与和结果0
[2,4,1]:与和结果0
[4]:与和结果100
[4,1]:与和结果0
[1]:与和结果1
综上,答案为0。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long longusing namespace std;int check(ull x)
{int ans = 0;while(x){if(x & 1) ans ++;x >>= 1;}return ans;
}int main()
{int n, k, ans = 0;cin >> n >> k;vector<int> a(n);for(auto &x : a)cin >> x;for(int i = 0; i < 1 << n; i ++){ull s = (1ull << 64) - 1;for(int j = 0; j < n; j ++)if(i >> j & 1) s &= a[j];if(check(s) == k) ans ++;}cout << ans << "\n";return 0;
}
D. 幂运算(高精度+欧拉函数)
输入
3 1223
输出
256
点击查看代码
#include<bits/stdc++.h>
#define int long longusing namespace std;int qmi(int a, int b, int mod)
{int ans = 1;while(b){if(b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;
}int get(int x)
{int ans = x;for(int i = 2; i < x / i; i ++){if(x % i == 0){ans = ans / i * (i - 1);while(x % i == 0)x /= i;}}if(x > 1)ans = ans / x * (x - 1);return ans;
}void solve()
{int n, m, p;cin >> n >> p;int ans = 2;for(int i = 1; i <= n; i ++)ans = ans * ans % p;cout << ans << "\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;while(T --)solve();return T ^ T;
}
J. 异次元抓捕(博弈)
输入1
2
1
617
输出1
YES
NO
说明
k=1的时候
黑色代表障碍 红色是行动轨迹 蓝色是每次移动可以走的位置 (不是最佳方案,仅供理解用)(解释仅供说明移动方式和摆放障碍的方式)
输入2
1
17
输出2
NO
点击查看代码
#include<bits/stdc++.h>using namespace std;void solve()
{int n, m;cin >> n;m = n - 1;if(n == 1) puts("YES");else puts("NO");
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while(T --)solve();return T ^ T;
}
K. 奖励关(贪心)
输入
2
1
3
输出
1
2
说明
当前攻击力等于 2i+3xj, i表示已执行操作2的次数 ,j表示当前攻击与上一次攻击间隔间的操作3的次数
点击查看代码
#include<bits/stdc++.h>
#define int long longusing namespace std;const int N = 110;int a[N], ans[N];
/*
2 4 8 16 32 64 128 256 512 1024 2048
4096 8192 16384 32768 65536 131072 262144
524288 1048576 2097152 4194304 8388608 16777216
33554432 67108864 134217728 268435456 536870912
1073741824 2147483648 4294967296 8589934592 17179869184 34359738368
*/void solve()
{int n, m = 1, s = 1, ans = 0;cin >> n;ans = 1;n --;ans += n / 2;cout << ans << "\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while(T --)solve();return T ^ T;
}
M. 找孙子(dfs枚举)
输入
5 10
5 3
2 3
1 2
4 1
1 3
4 2
2 5
4 3
1 5
4 5
输出
3 1 0 6 0
说明
点击查看代码
#include<bits/stdc++.h>
#define int long longusing namespace std;void solve()
{int n, m, a, b;cin >> n >> m;vector<int> g[n + 1], ans(n + 1);for(int i = 1; i <= m; i ++){cin >> a >> b;g[a].push_back(b);
// g[b].push_back(a);}for(int i = 1; i <= n; i ++){int t = g[i].size(), s = 0;for(auto x : g[i]){if(x != i)s += g[x].size();
// s += t;}ans[i] = s;}for(int i = 1; i <= n; i ++)cout << ans[i] << ' ';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;while(T --)solve();return T ^ T;
}