A.骰子
规律
#include <iostream> #include<cstdio> typedef long long ll; using namespace std; ll dp[5][100005],sum[5][100005]; ll n,m; void init(){ dp[1][1]=1,dp[1][2]=5,dp[1][3]=6,dp[1][4]=2; for(ll i=1;i<=n;i++){ ll tmp=i%4; if(tmp==0) tmp=4; dp[1][i]=dp[1][tmp]; sum[1][i]=sum[1][i-1]+dp[1][i]; } dp[2][1]=5,dp[2][2]=6,dp[2][3]=8; dp[2][4]=9;dp[2][5]=8;dp[2][6]=6; for(ll i=1;i<=n;i++){ ll tmp=i%6; if(tmp==0) tmp=6; dp[2][i]=dp[2][tmp]; sum[2][i]=sum[2][i-1]+dp[2][i]; } dp[3][1]=11; for(ll i=1;i<=n;i++){ ll tmp=i%1; if(tmp==0) tmp=1; dp[3][i]=dp[3][tmp]; sum[3][i]=sum[3][i-1]+dp[3][i]; } dp[4][1]=14; for(ll i=1;i<=n;i++){ ll tmp=i%1; if(tmp==0) tmp=1; dp[4][i]=dp[4][tmp]; sum[4][i]=sum[4][i-1]+dp[4][i]; } } int main() { scanf("%lld%lld",&n,&m); init(); ll x=m/4; ll r=m%4; ll ans=sum[4][n]*x; if(r) ans+=sum[r][n]; printf("%lld ",ans); return 0; }
D.zzs妹子
排序+优先队列
#include <iostream> #include<cstdio> #include<queue> #include<algorithm> using namespace std; struct Node{ int l,r; bool operator <(const Node& b)const{ return r>b.r; } }node[200005]; priority_queue<Node> q; bool cmp(Node a,Node b){ if(a.l!=b.l) return a.l<b.l; else return a.r<b.r; } int main() { int n;scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&node[i].l,&node[i].r); } sort(node+1,node+1+n,cmp); int ans=0; for(int i=1;i<=n;i++){ if(q.empty()) {ans++;q.push(node[i]);continue;} Node top=q.top(); if(node[i].l>top.r) {q.pop();q.push(node[i]);} else {ans++;q.push(node[i]);} } printf("%d ",ans); return 0; }
B.子序列 II
树状数组
#include <iostream> #include<cstdio> #include<algorithm> #include<cstring> #define mod 1000000007 #define lowbit(x) x&(-x) typedef long long ll; using namespace std; ll n,t; ll a[200005],b[200005],c[200005]; ll pre_smaller[200005],pre_bigger[200005]; ll after_smaller[200005],after_bigger[200005]; inline ll getid(ll x){return lower_bound(b+1,b+1+t,x)-b;} void add(ll pos,ll val){ for(ll i=pos;i<=n;i+=lowbit(i)) c[i]+=val; } ll getsum(ll pos){ ll ret=0; for(ll i=pos;i>0;i-=lowbit(i)) ret+=c[i]; return ret; } int main() { scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); t=unique(b+1,b+1+n)-(b+1); for(ll i=1;i<=n;i++){ ll id=getid(a[i]); add(id,1); pre_smaller[i]=getsum(id-1); pre_bigger[i]=i-getsum(id); } memset(c,0,sizeof(c)); for(ll i=n;i>=1;i--){ ll id=getid(a[i]); add(id,1); after_smaller[i]=getsum(id-1); after_bigger[i]=(n-i+1)-getsum(id); } ll ans=0; for(ll i=1;i<=n;i++){ ans=(ans+pre_smaller[i]*after_bigger[i]%mod)%mod; ans=(ans+pre_bigger[i]*after_smaller[i]%mod)%mod; } ans=ans%mod; printf("%lld ",ans); return 0; }
A.冠军剑士
bfs
#include <iostream> #include<cstdio> #include<cstring> #include<queue> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; ll m,n,x1,y1,x2,y2,k; ll Map[105][105]; ll vis[105][105]; ll dire[4][2]={0,-1,-1,0,0,1,1,0}; struct Node{ll x,y,dis;}; void setbomb(ll x,ll y){ for(ll i=max(x-1,(ll)1);i<=min(x+1,n);i++){ for(ll j=max(y-1,(ll)1);j<=min(y+1,m);j++){ Map[i][j]=-1; } } } bool in(ll x,ll y){ return x>=1&&x<=n&&y>=1&&y<=m; } ll bfs(ll x,ll y){ queue<Node> q; while(!q.empty()) q.pop(); q.push(Node{x,y,0});vis[x][y]=1; while(!q.empty()){ Node now=q.front();q.pop(); if(now.x==x2&&now.y==y2) return now.dis; for(ll i=0;i<4;i++){ ll nx=now.x+dire[i][0]; ll ny=now.y+dire[i][1]; if(in(nx,ny)&&!vis[nx][ny]&&Map[nx][ny]!=-1){ q.push(Node{nx,ny,now.dis+1}); vis[nx][ny]=1; } } } return 0; } int main() { scanf("%lld%lld%lld%lld%lld%lld%lld",&m,&n,&x1,&y1,&x2,&y2,&k); swap(n,m); for(ll i=1;i<=k;i++){ ll x,y;scanf("%lld%lld",&x,&y); setbomb(x,y); } ll ans=bfs(x1,y1); printf("%lld ",ans); return 0; }
C.新校游乐场
01背包
#include <iostream> #include<cstdio> using namespace std; int n,t; int v[1005],w[1005],dp[1005]; int main() { scanf("%d%d",&n,&t); for(int i=1;i<=n;i++){ scanf("%d%d",&v[i],&w[i]); } for(int i=1;i<=n;i++){ for(int j=t;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } printf("%d ",dp[t]); return 0; }
B.帝国交通