[牛客练习赛60] ABCD
A:
涉及知识点： 位运算
解法： &运算对应的二进制运算，如果第i个数的二进制第k位为1，那么它可以和其余所有二进制第k位为1的每一个数产生(1<<i)的贡献(当然也包括它本身)，所以统计二进制第k位为1的个数，最后加一下
时间复杂度： O(nlogn)
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long ll a[35]; int main() { int n,x; ll ans = 0; cin>>n; for(int i=1;i<=n;i++){ cin>>x; int cnt = 0; while(x){ int z = x%2; x /= 2; a[cnt++] += z; } } for(int i=0;i<=30;i++) ans += (1ll*(1<<i)*a[i]*a[i]); cout<<ans<<endl; return 0; }
B:
涉及知识点： 计数
解法： n个点，任意两点之间都可以形成唯一一条直线，那么取任意一条直线，这条直线可以和剩余的n-2个点，形成n-2个不相同的三角形，所以一条边可以对所有三角形的周长产生(n-2)次的贡献
时间复杂度：O(n^2)
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 1005; ll a[maxn],b[maxn]; const ll mod = 998244353; int main() { ll n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]>>b[i]; ll ans = 0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ ans += 1ll*((abs(a[i] - a[j]) + abs(b[i] - b[j]))*(n - 2)); ans %= mod; } } cout<<ans<<endl; return 0; }
C:
涉及知识点： dp
解法： 只会写O(26
我们设dp[ i ][ j ]表示前i个字母组成长度为j的子序列的个数 那么dp[ i ][ j ]就等于dp[ i-1 ][ j-1 ] + dp[ i-1 ][ j ],那么重复的其实就等于上一个s[i]的位置记为pos，即dp[ pos-1 ][ j-1 ]的个数，减去即可，为了防止等于负数，记得先加上mod)的dp，如果n再大一点的话，就t了，然后又补一个O(
时间复杂度： O(
代码：
//这是O(26n^2)的代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 +7;
ll dp[1005][1005][30];
char s[1005];
int main()
{
int n,m;
cin>>n>>m;
scanf("%s",s+1);
if(m == 0){
cout<<"1"<<endl;
return 0;
}
for(int i=1;i<=n;i++){
dp[i][1][s[i]-'a'] = 1;
for(int j=1;j<=m;j++){
for(int k=0;k<26;k++){
if(s[i] == 'a' + k){
for(int z=0;z<26;z++)
dp[i][j][k] += (dp[i-1][j-1][z]),dp[i][j][k]%=mod;
}
else
dp[i][j][k] += dp[i-1][j][k],dp[i][j][k]%=mod;
}
}
}
ll ans = 0;
for(int i=0;i<26;i++)
ans += dp[n][m][i],ans%=mod;
cout<<ans<<endl;
return 0;
}//这是O(n^2)的代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const int maxn = 1005;
char s[maxn];
int pre[maxn];
ll dp[maxn][maxn];
int main()
{
int n,k;
scanf("%d %d",&n,&k);
scanf("%s",s+1);
dp[0][0] = 1;
for(int i=1;i<=n;i++){
dp[i][0] = 1;
for(int j=1;j<=i;j++){
dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
if(pre[s[i]-'a'])
dp[i][j] = (dp[i][j] - dp[pre[s[i]-'a'] - 1][j-1] + mod)%mod;
dp[i][j] %= mod;
}
pre[s[i]-'a'] = i;
}
printf("%lld\n",dp[n][k]%mod);
return 0;
}
D:
涉及知识点： 同余/扩展欧几里得
解法： 可以将方程移项得到 ax + by = k - cz ,由于方程组一定有解，我们枚举z，这就变成了典型的扩展欧几里得，显然 (k - cz)%gcd(a , b) 等于 0 才有解，然后根据exgcd求出最小的y，最后求得x，如果 x 或者 y 小于 0 ，继续遍历...
时间复杂度： 不会算呀QAQ
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long //扩展欧几里得,求ax+by=d,d是a和b的最大公约数 ll exgcd(ll a,ll b,ll &x,ll &y) { if(!b){ x = 1,y = 0; return a; } ll d = exgcd(b , a%b , y , x); y -= (a/b)*x; return d; } int main() { ll a,b,c,k; cin>>a>>b>>c>>k; ll gc = __gcd(a , b); for(int i=0;i<=k/c;i++) { if((k - c*i)%gc != 0)continue ; ll x,y; ll d = exgcd(a ,b , x, y); x = (k-c*i)*x/gc; x = (x%(b/d) + (b/d))%(b/d); y = (k - a*x - c*i)/b; if(x < 0 || y < 0) continue ; cout<<x<<" "<<y<<" "<<i<<endl; break ; } return 0; }顺便放一下给出方程组：ax + by = k ,a , b, k都已知的情况下，求最小的x的模板：
#include <bits/stdc++.h> using namespace std; #define ll long long //扩展欧几里得,求ax+by=d,d是a和b的最大公约数 ll exgcd(ll a,ll b,ll &x,ll &y) { if(!b){ x = 1,y = 0; return a; } ll d = exgcd(b , a%b , y , x); y -= (a/b)*x; return d; } int main() { ll a,b,k; cin>>a>>b>>k; if(k%__gcd(a,b)) cout<<"Impossible"<<endl; else{ ll c,d; ll gc = exgcd(a,b,c,d); c = k*c/gc; ll ans = (c%(b/gc) + (b/gc))%(b/gc); cout<<ans<<endl; } return 0; }
acm菜鸡日常 文章被收录于专栏
一般写一些打过的比赛题解以及不会的算法
