牛客练习赛60
A-大吉大利
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
#define scanf1(a) scanf("%d",&a)
#define scanf2(a,b) scanf("%d%d",&a,&b)
#define mes(a,b) memset(a,b,sizeof a)
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
ll a[100005],b[100005],n,temp,cnt;
ll ans=0;
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans*=a;
a*=a;
b>>=1;
}
return ans;
}
int main() {
js;
cin>>n;
for(int i=0;i<n;++i) {
cin>>a[i];
temp=a[i],cnt=0;
while(temp) {
if(temp&1) b[cnt]++;
++cnt;
temp>>=1;
}
}
for(int i=0;i<n;++i) {
cnt=0;
while(a[i]) {
if(a[i]&1) ans+=b[cnt]*qpow(2,cnt);
++cnt;
a[i]>>=1;
}
}
cout<<ans<<endl;
}B-三角形周长和
数据保证三点补共线，我们先任取2点形成一条边，那么剩下n-2个点，都可以和这两点形成一个三角形，也就是说每个边都会出现n-2次，直接边输入边计算就可以了，代码如下（%其实挺慢的）：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
#define scanf1(a) scanf("%d",&a)
#define scanf2(a,b) scanf("%d%d",&a,&b)
#define mes(a,b) memset(a,b,sizeof a)
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
struct node{
ll x,y;
}q[1005];
ll ans=0,cnt,n;
int main() {
js;
cin>>n;
cnt=n-2;
for(int i=1;i<=n;++i) {
cin>>q[i].x>>q[i].y;
for(int j=1;j<i;++j) {
ans+=(abs(q[i].x-q[j].x)+abs(q[i].y-q[j].y))*cnt;
while(ans>=998244353) ans-=998244353;
}
}
while(ans>=998244353) ans-=998244353;
cout<<ans<<endl;
}C-操作集锦
dp[i][j]表示考虑前i个字符形成的长度为j的子序列个数。
状态转移方程为：dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
当有相同的字符出现时还要去掉重复的部分，而这一部分被包括在dp[i-1][j-1]；
用pre[i]记录s[i]最近一次出现的位置，
因为+dp[i-1][j-1]表示前i-1个字符组成的长度为j-1的子序列后面加上s[i],
故多出来的就是dp[pre[s[i]-'a']-1][j-1];
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
#define scanf1(a) scanf("%d",&a)
#define scanf2(a,b) scanf("%d%d",&a,&b)
#define mes(a,b) memset(a,b,sizeof a)
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int mod = 1e9 + 7;
ll dp[1005][1005];
int n,k,pre[1005];
char s[1005];
int main() {
js;
cin>>n>>k;
cin>>(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[pre[s[i]-'a']-1][j-1];
dp[i][j]%=mod;
}
pre[s[i]-'a']=i;
}
ll ans=dp[n][k];
if(ans<0) ans+=mod;
cout<<ans<<endl;
}D-斩杀线计算大师
最短路bcj目前看不懂，不会写。
ax+by=c,有解的充要条件是gcd(a,b)|c,即a，b的最大公约数能被c整除。
对ai+bx+cy=k;可以遍历i，转化为二元bx+cy=k-ai,k-ai>=0,如果不满足gcd(b,c)|(k-ai)就跳过。
由ax+by=gcd(a,b)得到解x，则bx+cy=k-ai的一个特解x=x*(k-ai)/gcd(b,c);
其中x模c不同余的解共有d个：
x的最小非负解为：
i和x都有了，y就简单了，最后判断x，y是否都是非负数就行了：
#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;
y=0;
return a;
}
ll r=exgcd(b,a%b,x,y);
ll temp=x;
x=y;
y=temp-(a/b)*y;
return r;
}
ll gcd(ll a,ll b){
if(a%b==0)return b;
return gcd(b,a%b);
}
int main(){
ll a,b,c,k,x,y,temp,sum;
js;
cin>>a>>b>>c>>k;
temp=gcd(b,c);
for(ll i=0;a*i<=k;++i) {
if((k-a*i)%temp!=0) continue;
sum=(k-a*i)/temp;
exgcd(b,c,x,y);
x*=sum;
x=(x%(c/temp)+(c/temp))%(c/temp);
y=(k-a*i-b*x)/c;
if(x<0||y<0) continue;
cout<<i<<" "<<x<<" "<<y<<endl;
break;
}
return 0;
}
