放那些不小心开了，写了或者抄了代码凑个题数又没什么放的意义的题。
1.P3110 [USACO14DEC]驮运Piggy Back 最短路水题。 跑三遍。
2.P3800 Power收集 dp水题
//Twenty
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<ctime>
const int maxn=4005;
typedef long long LL;
using namespace std;
int n,m,kk,tt,dp[maxn];
struct node {
int x,y,v;
friend bool operator <(const node &A,const node&B) {
return A.x<B.x||(A.x==B.x&&A.y<B.y);
}
}p[maxn];
template<typename T> void read(T &x) {
char ch=getchar(); T f=1; x=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
x*=f;
}
void work() {
sort(p+1,p+kk+1);
int ans=-1e9;
for(int i=1;i<=kk;i++) {
dp[i]=p[i].v;
for(int j=1;j<i;j++)
if((p[i].x-p[j].x)*tt>=abs(p[i].y-p[j].y))
dp[i]=max(dp[i],dp[j]+p[i].v);
ans=max(ans,dp[i]);
}
printf("%d
",ans);
}
void init() {
read(n);
read(m);
read(kk);
read(tt);
for(int i=1;i<=kk;i++) {
read(p[i].x);
read(p[i].y);
read(p[i].v);
}
}
int main() {
init();
work();
return 0;
}
3.小魔女帕琪
手动艾特llj大佬
答案为所有长度为7的区间是七重奏的期望之和。
每个区间相互独立。
tarjan水题。发现自己越来越喜欢stl了，queue和stack就不说了，最近一言不合就上vector,set,lower_bound什么的。
//Twenty
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<ctime>
#include<stack>
typedef long long LL;
using namespace std;
const int maxm=50005;
int n,m;
template<typename T> void read(T &x) {
char ch=getchar(); T f=1; x=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
x*=f;
}
int ecnt,fir[maxm],nxt[maxm<<1],to[maxm<<1];
void add(int u,int v) {
nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;
}
stack<int>sta;
vector<int>vc[maxm],ans;
int dfn[maxm],low[maxm],dfs_clock,sccono[maxm],scc,mxsz;
void tarjan(int x) {
dfn[x]=low[x]=++dfs_clock;
sta.push(x);
for(int i=fir[x];i;i=nxt[i]) {
int y=to[i];
if(!dfn[y]) {
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(!sccono[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]) {
scc++;
int sz=0;
for(;;) {
int u=sta.top();
sta.pop();
sz++;
sccono[u]=scc;
vc[scc].push_back(u);
if(u==x) break;
}
if(sz>mxsz) {
ans.clear();
ans.push_back(scc);
mxsz=sz;
}
else if(sz==mxsz) ans.push_back(scc);
}
}
int up=0,len=0;
int cmp(int x,int y) {
for(int i=0;i<len;i++)
if(vc[ans[x]][i]>vc[ans[y]][i]) return 1;
return 0;
}
void work() {
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
int as=ans[0]; up=ans.size(); len=vc[as].size();
for(int i=1;i<up;i++) {
if(cmp(i,as)) as=i;
}
sort(vc[as].begin(),vc[as].end());
printf("%d
",len);
for(int i=0;i<len;i++)
printf("%d ",vc[as][i]);
printf("
");
}
void init() {
read(n); read(m);
for(int i=1;i<=m;i++) {
int o,x,y;
read(x); read(y); read(o);
add(x,y);
if(o==2) add(y,x);
}
}
int main() {
#ifdef DEBUG
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
init();
work();
return 0;
}