1.签到:https://ac.nowcoder.com/acm/contest/78904/A
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main()
{
for(int i=1;i<=6;i++) cin>>a[i];
int sum=0;
for(int i=1;i<=6;i++) sum+=a[i];
if(30*a[1]<sum) cout<<"Yes";
else cout<<"No";
}
2.贪心:https://ac.nowcoder.com/acm/contest/78904/B
AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[100010];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int ck=0;
for(int i=1;i<=n;i++)
{
ck=(ck+a[i])%k;
}
sort(a+1,a+n+1,cmp);
int cnt=0;
k=ck;
for(int i=1;i<=n;i++)
{
if(a[i]>=k)
{
cnt++;
break;
}
cnt++;
k-=a[i];
}
cout<<cnt-(k==0);
}
3.枚举:https://ac.nowcoder.com/acm/contest/78904/E
AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,p,x;
int main()
{
cin>>n>>m>>p>>x;
int cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(x-i*j>0)
{
if((x-i*j)%(2*(i+j))==0)
{
int ww=(x-i*j)/(2*(i+j));
if(ww<=p) cnt++;
}
}
}
}
cout<<cnt;
}
4.同余最短路/带预处理的完全背包:
https://ac.nowcoder.com/acm/contest/78904/D
好像就是寒假牛客训练的卡牌那一个:
1.同余最短路:
我们对于 p 个编号为0,1,⋯,p−1 的点,进行连边:编号为 i 的点向编号为 (i+a1)%p....(i+an)%p 的点连边。每经过一条边,相当于选了一个物品,也就是权位1。
然后我们从每个点出发BFS即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,p;
queue<pair<int,int> > q;
int vis[2020];
int c[2020];
int main(){
cin>>n>>p;
for (int i=1;i<=n;i++) {
int x;
cin>>x;
if(vis[x%p]==0)
{
vis[x%p]=1;
q.push({x%p,1});
c[x%p]=1;
}
}
while (!q.empty()) {
int pos=q.front().first,num=q.front().second;
q.pop();
if (pos==0)
{
cout<<num;
return 0;
}
for (int i=0;i<p;i++) {
if(c[i])
{
int ck=(i+pos)%p;
if(vis[ck]) continue;
vis[ck]=1;
q.push({ck,num+1});
}
}
}
}
2.预处理的完全背包:
首先参考牛客B站视频的DP过了95%(数据有点水),原因在于它有一点不同于完全背包,就是%p后可能变得跟小,因此我们还要回过头考虑前面的,因此在内部还要加一层循环。
我们考虑预处理出su[i]表示走i步所要的min次数(注意这里的min只考虑了同一个物品,比如选1个还是选2个,不是选一个1再选一个2)
这样子,原来a[2*a1%p]...a[n*a1%p]就包含在了su[i]中,因此我们把su[i]当成元素枚举即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,p;
int a[2020],dp[2020],su[2010];
int main()
{
cin>>n>>p;
memset(dp,0x3f,sizeof(dp));
memset(su,0x3f,sizeof(su));
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]%=p;
}
for(int i=1;i<=n;i++)
{
int cur=a[i];
for(int j=1;j<=p;j++) su[(j*cur)%p]=min(j,su[(j*cur)%p]);
}
for(int i=0;i<p;i++) dp[i]=su[i];
for(int i=0;i<p;i++)
{
int cost=su[i];
for(int j=0;j<p;j++) dp[(i+j)%p]=min(cost+dp[j],dp[(i+j)%p]);
}
cout<<dp[0];
}
5.线段树:https://ac.nowcoder.com/acm/contest/78904/F
带了懒标记的线段树,维护A,B以及A和B共有的1的即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,q;
string A,B;
int a[100010],b[100010];
struct node{
int l,r;
int c1,c2,c;//c1:A字符串1的个数,c2:B字符串1的个数,c:同时为1的个数
int lz1,lz2;
}tr[404040];
void push_up(int u)
{
tr[u].c1=tr[u<<1].c1+tr[u<<1|1].c1;
tr[u].c2=tr[u<<1].c2+tr[u<<1|1].c2;
tr[u].c=tr[u<<1].c+tr[u<<1|1].c;
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u] = {l,r,a[l],b[l],a[l]&b[l]};
return;
}
tr[u]={l,r};
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
push_up(u);
}
void push_down(int u)
{
if(tr[u].lz1==1)
{
tr[u].lz1=0;
tr[u<<1].lz1=1;
tr[u<<1|1].lz1=1;
tr[u<<1].c1=(tr[u<<1].r-tr[u<<1].l+1);
tr[u<<1].c=tr[u<<1].c2;
tr[u<<1|1].c1=(tr[u<<1|1].r-tr[u<<1|1].l+1);
tr[u<<1|1].c=tr[u<<1|1].c2;
}
if(tr[u].lz2==1)
{
tr[u].lz2=0;
tr[u<<1].lz2=1;
tr[u<<1|1].lz2=1;
tr[u<<1].c2=(tr[u<<1].r-tr[u<<1].l+1);
tr[u<<1].c=tr[u<<1].c1;
tr[u<<1|1].c2=(tr[u<<1|1].r-tr[u<<1|1].l+1);
tr[u<<1|1].c=tr[u<<1|1].c1;
}
}
void modify(int u,int l,int r,int op)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
if(op==1)
{
tr[u].c1=tr[u].r-tr[u].l+1;
tr[u].c=tr[u].c2;
tr[u].lz1=1;
}
else{
tr[u].c2=tr[u].r-tr[u].l+1;
tr[u].c=tr[u].c1;
tr[u].lz2=1;
}
return;
}
push_down(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(mid>=l) modify(u<<1,l,r,op);
if(mid<r) modify(u<<1|1,l,r,op);
push_up(u);
}
int main()
{
cin>>n>>A>>B>>q;
for(int i=0;i<n;i++)
{
a[i+1]=A[i]-'0';
b[i+1]=B[i]-'0';
}
build(1,1,n);
while(q--)
{
char op;
int l,r;
cin>>op>>l>>r;
int x=op-'A'+1;
modify(1,l,r,x);
cout<<tr[1].c<<endl;
}
}