【题解】牛客算法周周练A-E
A 小A买彩票
前言：开始以为这是一道可以通过计算算出来的题，后来想想不对，看到n这么小，应该就是概率dp了，在这道题上也可以看作暴力。
思路：dp[i][j]表示前i张彩票，中奖总金额为j的概率的次数。
转移方程： ，其中k是1~4的数。
为什么是这样？我们可以理解为，之后能抽到的总奖金j，是从之前的总奖金加上新的彩票得到的，新的彩票金额只有1到4，所以转移就是理所当然的了。
处理完dp后，统计大于等于n*3的次数总和sum，我们把一共的情况记为tot,tot就等于4^n。答案就是：sum/tot。
为什么tot是4^n？因为每次都往外延伸4种情况，可以理解为一颗树一样，对于每次结果都可以往外再延伸4种，所以就是总情况每次都会乘4了。
最后用gcd处理一下答案约分即可。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=2e3+5;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
ll dp[50][150];
int main(){
int n;
scanf("%d",&n);
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=4*i;j++){
for(int k=1;k<=4;k++){
if(j>=k) dp[i][j]+=dp[i-1][j-k];
}
}
}
ll ans=0;
for(int i=n*3;i<=n*4;i++){
ans+=dp[n][i];
}
ll sum=pow(4,n);
printf("%lld/%lld",ans/gcd(ans,sum),sum/gcd(ans,sum));
return 0;
}B 「金」点石成金
思路：看到n是15，直接dfs暴力枚举就好了，一共也就2^15个情况。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=1e5+5;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
ll a[maxn],b[maxn],c[maxn],d[maxn];
int n;
ll ans=0;
void dfs(int u,ll cf,ll mf){
if(u==n+1){
ans=max(ans,cf*mf);
return ;
}
dfs(u+1,cf+a[u],max(0ll,mf-b[u]));
dfs(u+1,max(0ll,cf-d[u]),mf+c[u]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld%lld",a+i,b+i,c+i,d+i);
}
dfs(1,0,0);
printf("%lld",ans);
return 0;
}C 小阳的贝壳
前言：这个题一开始我被gcd卡了，对辗转相除法的理解不够深，也对取模的理解不够深。
思路：很明显的线段树了，不过比较有意思的是，这个题是维护差分数组的线段树。
线段树维护3个值，val:维护相邻最大差，sum:维护前缀和，gcd:维护gcd。
更新就不用多讲了，就是差分数组的更新，把l和r+1单点更新一下就行，也就是update(l,x) update(r+1,-x)。
最大差也很简单，只需要找到刚刚维护的val最大值就行，不过要找l+1到r。
这里主要讲讲gcd:因为gcd(a,b)=gcd(a,b%a)，同理gcd(a,b)=gcd(a,b-a)，为什么，因为b%a其实相当于b-k*a，b-a和b%a都是在一个同余系里面，所以他们的gcd都是一样的，不过有可能出现负数，只需要取一个abs就行了。
所以假设求gcd(a,b,c)，那就等于gcd(a,b-a,c-b)，可以看出可以通过统计后面的差分gcd，再跟第一个数做一下gcd就可以了（是第一个数，不是差分数组第一个数，要求一下和）。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=1e5+5;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
#define lson rt << 1 // == rt * 2 ×ó¶ù×Ó
#define rson rt << 1 | 1 // == rt * 2 + 1 ÓÒ¶ù×Ó
#define int_mid int mid = tree[rt].l + tree[rt].r >> 1
ll a[maxn];
int n;
struct Node{
int l,r;
ll val,sum,gcd;
};
struct Segment_Tree{
Node tree[maxn*4];
void push_up(int rt){
tree[rt].sum=tree[lson].sum+tree[rson].sum;
tree[rt].val=max(abs(tree[lson].val),abs(tree[rson].val));
tree[rt].gcd=__gcd(tree[lson].gcd,tree[rson].gcd);
}
void build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){
tree[rt].val=a[l];
tree[rt].gcd=a[l];
tree[rt].sum=a[l];
return ;
}
else{
int mid=l+r>>1;
build(lson,l,mid);
build(rson,mid+1,r);
push_up(rt);
}
}
void update(int rt,int pos,ll val){
if(tree[rt].l==tree[rt].r&&pos==tree[rt].l){
tree[rt].val+=val;
tree[rt].gcd+=val;
tree[rt].sum+=val;
return ;
}
//if(tree[rt].l==tree[rt].r) return ;
int_mid;
if(pos<=mid) update(lson,pos,val);
else update(rson,pos,val);
push_up(rt);
}
ll query_sum(int rt,int l,int r){
if(l<=tree[rt].l&&r>=tree[rt].r) return tree[rt].sum;
int_mid;
if(r<=mid) return query_sum(lson,l,r);
else if(l>mid) return query_sum(rson,l,r);
else return query_sum(lson,l,mid)+query_sum(rson,mid+1,r);
}
ll query_max(int rt,int l,int r){
if(l<=tree[rt].l&&r>=tree[rt].r) return abs(tree[rt].val);
int_mid;
if(r<=mid) return query_max(lson,l,r);
else if(l>mid) return query_max(rson,l,r);
else return max(query_max(lson,l,mid),query_max(rson,mid+1,r));
}
ll query_gcd(int rt,int l,int r){
if(l<=tree[rt].l&&r>=tree[rt].r) return tree[rt].gcd;
int_mid;
ll ans=0;
if(mid>=l) ans=query_gcd(lson,l,r);
if(mid<r) ans=__gcd(ans,query_gcd(rson,l,r));
return ans;
}
};
Segment_Tree stree;
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
}
for(int i=n;i>=1;i--){
a[i]=a[i]-a[i-1];
}
stree.build(1,1,n+1);
while(q--){
int t,l,r,x;
scanf("%d",&t);
if(t==1){
scanf("%d%d%d",&l,&r,&x);
stree.update(1,l,x);
stree.update(1,r+1,-x);
}
else if(t==2){
scanf("%d%d",&l,&r);
if(l==r){
printf("0\n");
continue;
}
printf("%lld\n",stree.query_max(1,l+1,r));
}
else{
scanf("%d%d",&l,&r);
ll sum=stree.query_sum(1,1,l);
printf("%lld\n",abs(__gcd(sum,stree.query_gcd(1,l+1,r))));
}
}
return 0;
}D Forsaken喜欢字符串
前言：这道题这么少人过，以为是个很难的题，结果一看是个很简单的题。
思路：题意就是说要求这个串的长度为k的所有子串和别的串的子串相等时的贡献和。但是这个k只有5。所以这道题完全可以暴力统计每个子串。我们可以用字符串哈希和map统计每个子串的出现次数，然后对于q次询问，就把刚刚统计的子串出现次数减去自己的串的子串出现次数再乘上长度就好了。
看了看别人的题解，发现不用字符串哈希都可以做，就直接把子串放进去map就行了。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=5e4+5;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
char s[maxn][10];
int n,k;
typedef unsigned long long ull;
ull hs[maxn],p[maxn];
const ull base=31;
map<ull,int> mp;
map<ull,int> cnt;
void Insert(char str[]){
hs[0]=str[0];
for(int i=1;i<k;i++){
hs[i]=hs[i-1]*base+(ull)str[i];
}
}
ull GetHash(int l,int r){
return (ull)hs[r]-p[r-l+1]*hs[l-1];
}
int main(){
scanf("%d%d",&n,&k);
p[0]=1;
for(int i=1;i<=k;i++){
p[i]=p[i-1]*base;
}
for(int i=1;i<=n;i++){
scanf("%s",s[i]);
Insert(s[i]);
for(int j=0;j<=k-1;j++){
for(int len=1;j+len-1<=k-1;len++){
mp[GetHash(j,j+len-1)]++;
}
}
}
int q;
scanf("%d",&q);
while(q--){
int x,len;
scanf("%d%d",&x,&len);
Insert(s[x]);
int ans=0;
cnt.clear();
for(int j=0;j+len-1<=k-1;j++){
cnt[GetHash(j,j+len-1)]++;
}
for(int j=0;j+len-1<=k-1;j++){
ans+=(mp[GetHash(j,j+len-1)]-cnt[GetHash(j,j+len-1)])*len;
}
printf("%d\n",ans);
}
return 0;
}E Board
前言：这道题其实是2019ICPC银川的签到题，不是很难，比较考验思维。
思路：我假设要求的点是“？”，他周围3个点是x1,x2,x3，他们的排布是这样的。
x1 x2
x3 ?
假设对于第一行的加的总和是a，对于第二行加的总和是b，对于第一列加的总和是c，对于第二列加的总和是d。
那么：x1=a+c x2=a+d x3=b+c ?=b+d
可以发现x1+?=x2+x3=a+b+c+d，因此?=x2+x3-x1。
如果这个点在左上角之类的位置怎么办，只需要把这个点移动到右下角就行了，通过整行整列的对换，换到右下角，再进行刚刚的处理就好。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=2e3+5;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
int mp[1010][1010];
int main(){
int n;
scanf("%d",&n);
int px=0,py=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&mp[i][j]);
if(mp[i][j]==-1){
px=i;py=j;
}
}
}
for(int i=1;i<=n;i++){
swap(mp[n][i],mp[px][i]);
}
for(int i=1;i<=n;i++){
swap(mp[i][n],mp[i][py]);
}
printf("%d",mp[n][1]+mp[1][n]-mp[1][1]);
return 0;
}
京东工作强度 208人发布
投递嘉士伯等公司10个岗位 >
