牛客练习赛60（ABCD）
A、大吉大利
考虑二进制的每一位，只有两位同时为1的数字取与操作，才会对答案贡献，直接枚举即可。（没乘 1LL WA一发）
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
int a[64];
int main()
{
int n;
sc("%d", &n);
for (int i = 0; i < n; i++)
{
int t;
sc("%d", &t);
for (int j = 0; j < 32; j++)
{
if (t & (1LL << j))
a[j]++;
}
}
ll ans = 0;
for (int j = 0; j < 32; j++)
{
if (a[j] == 0)
continue;
ll cnt = 1LL * a[j] * a[j];
ll num = 1LL << j;
ans += cnt * num;
}
pr("%lld\n", ans);
} B、三角形周长和
可以发现每条边的使用次数是确定的，所以枚举一下两个点构成的边即可。（没看到取模 WA 一发）
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1005;
struct node
{
ll x;
ll y;
}a[MAXN];
const ll mod = 998244353;
int main()
{
int n;
sc("%d", &n);
for (int i = 0; i < n; i++)
{
sc("%lld%lld", &a[i].x, &a[i].y);
}
ll ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
ans = (ans + abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y)) % mod;
}
}
ans = ans * (n - 2) % mod;
pr("%lld\n", ans);
} C、操作锦集
看到子序列的时候，总是想着自动机，过了很久发现是个dp，考虑长度从低枚举到高，每个位置的贡献等于取这个位置作为结尾的本质不同的子序列的数量，容易发现，如果前面出现过当前字母的话，有重复贡献，重复贡献就是之前位置构成长度为当前长度减一子序列的数量。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const ll mod = 1e9 + 7;
int book[30];
ll dp[1005][1005];
char s[1005];
int main()
{
int n, k;
sc("%d%d", &n, &k);
sc("%s", s + 1);
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
dp[i][0] = 1;
for (int j = 1; j <= k; j++)
{
if (book[s[i] - 'a'] == 0)
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
else
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] - dp[book[s[i] - 'a'] - 1][j - 1] + mod) % mod;
}
book[s[i] - 'a'] = i;
}
pr("%lld\n", dp[n][k]);
} D、斩杀线计算大师
ax+by+cz=k
由于题目保证有解，所以考虑枚举一维，将他变成 exgcd ，然后直接套板子，并在将 x 变成最小正整数解的前提下，判断 y 是否是非负数
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll exgcd(ll a, ll b, ll& x, ll& y) ///ax+by = gcd(a,b);
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll gcd = exgcd(b, a % b, x, y);
ll tmp = x;
x = y;
y = tmp - a / b * (y);
return gcd;
}
int main()
{
ll a, b, c, k;
sc("%lld%lld%lld%lld", &a, &b, &c, &k);
for (ll i = 0; i <= 1e5; i++)
{
ll kk = k - a * i;
if (kk < 0)
continue;
ll x, y;
ll g = exgcd(b, c, x, y);
if (kk % g != 0)
continue;
x *= kk / g;
x = (x % (c / g) + c / g) % (c / g);
y = (kk - b * x) / c;
if (x >= 0 && y >= 0)
{
pr("%lld %lld %lld\n", i, x, y);
return 0;
}
}
} 
投递中国石油等公司10个岗位 >