A
水
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <list>
#include <map>
#include <stack>
#include <vector>
#include <cstring>
#include <sstream>
#include <string>
#include <cmath>
#include <queue>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=;
const int MOD = 1e9+;
#define LL long long
void fre() {
freopen("in.txt","r",stdin);
}
inline int r() {
int x=,f=;char ch=getchar();
while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<='') { x=x*+ch-'';ch=getchar();}return x*f;
} int main(){
int T;
T=r();
while(T--){
int x,y;
int ans;
x=r();
y=r();
if(x%y!=)
ans=x/y+;
else
ans=x/y;
cout<<ans<<endl;
}
return ;
}
C
最短路
反向建边，记录当前点序号最小的前驱
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <list>
#include <map>
#include <stack>
#include <vector>
#include <cstring>
#include <sstream>
#include <string>
#include <cmath>
#include <queue>
#include <bits/stdc++.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=;
const int MOD = 1e9+;
#define LL long long
void fre() {
freopen("in.txt","r",stdin);
}
inline int r() {
int x=,f=;char ch=getchar();
while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<='') { x=x*+ch-'';ch=getchar();}return x*f;
}
int n,m;
struct node{
int v,c;
node(int vv,int cc){
v=vv;
c=cc;
}
node(){}
bool operator <(const node &r) const{
return c>r.c;
}
}; struct edge{
int v,cost;
edge(int vv=,int ccost =):v(vv),cost(ccost){}
}; vector<edge>e[N];
bool vis[N];
int dist[N];
int p[N];
void dij(int start){
clc(vis,false);
for(int i=;i<=n+;i++) dist[i]=inf;
priority_queue<node>q;
while(!q.empty()) q.pop();
dist[start]=;
q.push(node(start,));
node tmp;
while(!q.empty()){
tmp=q.top();
q.pop();
int u=tmp.v;
if(vis[u]) continue;
vis[u]=true;
for(int i=;i<e[u].size();i++){
int v=e[u][i].v;
int cost=e[u][i].cost;
if(!vis[v]&&dist[v]>dist[u]+cost){
dist[v]=dist[u]+cost;
p[v]=u;
q.push(node(v,dist[v]));
}
else if(!vis[v]&&dist[v]==dist[u]+cost){
p[v]=min(p[v],u);
}
}
}
}
void add(int u,int v,int w){
e[u].push_back(edge(v,w));
} void init(){
for(int i=;i<=n+;i++){
e[i].clear();
}
clc(p,-);
} int main(){
// fre();
int T;
T=r();
while(T--){
n=r(),m=r();
init();
int u,v,w;
while(m--){
u=r(),v=r(),w=r();
add(v,u,w);
}
dij(n+);
if(dist[]>=inf){
printf("-1\n");
continue;
}
else if(p[]==n+){
printf("0\n");
continue;
}
else
printf("%d\n",p[]);
}
return ;
}
D
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <list>
#include <map>
#include <stack>
#include <vector>
#include <cstring>
#include <sstream>
#include <string>
#include <cmath>
#include <queue>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=;
const int MOD = 1e9+;
#define LL long long
void fre() {
freopen("in.txt","r",stdin);
}
inline int r() {
int x=,f=;char ch=getchar();
while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<='') { x=x*+ch-'';ch=getchar();}return x*f;
}
struct node{
int s,w,num;
}p[N];
int n,R,q;
node a[N],b[N]; bool cmp(const node &a,const node &b){
return (a.s==b.s)?(a.num<b.num):(a.s>b.s);
} void work(){
int ai=,bi=;
for(int i=;i<=*n;i+=){
if(p[i].w>p[i+].w){
p[i].s++;
a[ai++]=p[i];
b[bi++]=p[i+];
}
else{
p[i+].s++;
a[ai++]=p[i+];
b[bi++]=p[i];
}
}
int i=,j=,k=;
while(i<ai&&j<bi){
if(cmp(a[i],b[j])){
p[k++]=a[i++];
}
else
p[k++]=b[j++];
}
while(i<ai) p[k++]=a[i++];
while(j<bi) p[k++]=b[j++];
} int main(){
// fre();
int T;
T=r();
while(T--){
n=r(),R=r(),q=r();
for(int i=;i<=*n;i++){
int x;
x=r();
p[i].s=x;
p[i].num=i;
}
for(int i=;i<=*n;i++){
int x;
x=r();
p[i].w=x;
}
sort(p+,p++*n,cmp);
for(int i=;i<=R;i++){
work();
}
printf("%d\n",p[q].num);
}
return ;
}
F
dp记忆话搜索
dp[i][j][k][inx][last]:当前三种水果分别有i j k个的时候且当前放第inx类的水果，持续了last天的方案数
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <list>
#include <map>
#include <stack>
#include <vector>
#include <cstring>
#include <sstream>
#include <string>
#include <cmath>
#include <queue>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=;
const int MOD = 1e9+;
#define LL long long
void fre() {
freopen("in.txt","r",stdin);
}
inline int r() {
int x=,f=;char ch=getchar();
while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<='') { x=x*+ch-'';ch=getchar();}return x*f;
} int num;
int dp[][][][][];
int a[],b[]; int dfs(int n,int a0,int a1,int a2,int inx,int last){
LL ans=;
if(dp[a0][a1][a2][inx][last]!=-) return dp[a0][a1][a2][inx][last];
if(n==num) return dp[a0][a1][a2][inx][last]=;
if(inx==-){
if(b[]>&&a0>=) ans+=dfs(n+,a0-,a1,a2,,);
if(b[]>&&a1>=) ans+=dfs(n+,a0,a1-,a2,,);
if(b[]>&&a2>=) ans+=dfs(n+,a0,a1,a2-,,);
}
else{
if(inx==){
if(last+<=b[]&&a0>=) ans+=dfs(n+,a0-,a1,a2,,last+);
if(b[]>&&a1>=) ans+=dfs(n+,a0,a1-,a2,,);
if(b[]>&&a2>=) ans+=dfs(n+,a0,a1,a2-,,);
}
else if(inx==){
if(last+<=b[]&&a1>=) ans+=dfs(n+,a0,a1-,a2,,last+);
if(b[]>&&a0>=) ans+=dfs(n+,a0-,a1,a2,,);
if(b[]>&&a2>=) ans+=dfs(n+,a0,a1,a2-,,);
}
else{
if(last+<=b[]&&a2>=) ans+=dfs(n+,a0,a1,a2-,,last+);
if(b[]>&&a0>=) ans+=dfs(n+,a0-,a1,a2,,);
if(b[]>&&a1>=) ans+=dfs(n+,a0,a1-,a2,,);
}
}
ans%=MOD;
return dp[a0][a1][a2][inx][last]=ans;
} int main(){
int T;
T=r();
while(T--){
clc(dp,-);
for(int i=;i<;i++){
// scanf("%d",&a[i]);
int x;
x=r();
a[i]=x;
}
for(int i=;i<;i++){
// scanf("%d",&b[i]);
int x;
x=r();
b[i]=x;
}
num=a[]+a[]+a[];
printf("%d\n",dfs(,a[],a[],a[],-,));
}
return ;
}