后两道题没交上去。。。md
T1
dijkstra+求哈密顿路径的水题，没开long long挂了两个点。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
const int N=50005,M=100005;
int n,m,ecnt,head[N],K,S,T,mst[11],dis[11][50005],f[1025][11];
bool vis[N];
struct Edge{
int to,nxt,val;
}e[M];
struct Node{
int id,dis;
bool operator < (const Node&rhs) const {
return dis>rhs.dis;
}
};
void didj(int s) {
memset(dis[s],0x3f,sizeof dis[s]);
memset(vis,0,sizeof vis);
priority_queue<Node>q;
q.push({mst[s],0});dis[s][mst[s]]=0;
while(!q.empty()) {
Node u=q.top();q.pop();
if(!vis[u.id]) {
vis[u.id]=1;
for(int i=head[u.id];i;i=e[i].nxt) {
int v=e[i].to;
if(dis[s][u.id]+e[i].val<dis[s][v]) {
dis[s][v]=dis[s][u.id]+e[i].val;
if(!vis[v]) q.push({v,dis[s][v]});
}
}
}
}
}
void dij(int s) {
queue<int>q;
q.push(mst[s]);memset(dis[s],0x3f,sizeof dis[s]);memset(vis,0,sizeof vis);
dis[s][mst[s]]=0;vis[mst[s]]=1;
while(!q.empty()) {
int u=q.front();q.pop();vis[u]=0;
for(int i=head[u];i;i=e[i].nxt ) {
int v=e[i].to;
if(dis[s][u]+e[i].val<dis[s][v]) {
dis[s][v]=dis[s][u]+e[i].val;
if(!vis[v]) vis[v]=1,q.push(v);
}
}
}
}
void add(int bg,int ed,int val) {e[++ecnt].nxt=head[bg];e[ecnt].to=ed;e[ecnt].val=val;head[bg]=ecnt;}
main() {
scanf("%lld%lld%lld%lld%lld",&n,&m,&K,&S,&T);
for(int i=1,a,b,c;i<=m;i++) {scanf("%lld%lld%lld",&a,&b,&c);add(a,b,c);}
for(int i=0;i<K;i++) {
scanf("%lld",&mst[i]);
dij(i);
}
mst[K]=S;
dij(K);
if(!K) {printf("%lld",(dis[K][T]==0x3f3f3f3f3f3f3f3f)?-1:dis[K][T]);return 0;}
memset(f,0x3f,sizeof f);
for(int i=0;i<K;i++) f[1<<i][i]=dis[K][mst[i]];
for(int i=0;i<1<<K;i++) {
for(int j=0;j<K;j++) {
if((i&(1<<j))) continue;
for(int k=0;k<K;k++){
if((!(i&(1<<k)))||k==j) continue;
f[i|(1<<j)][j]=min(f[i|(1<<j)][j],f[i][k]+dis[k][mst[j]]);
}
}
}
int ans=0x3f3f3f3f3f3f3f3f;
// cout<<ans<<endl;
for(int i=0;i<K;i++) {
ans=min(ans,f[(1<<K)-1][i]+dis[i][T]);
}
ans=(ans>=0x3f3f3f3f3f3f3f3)?-1:ans;
cout<<ans<<endl;
}
T2
优先队列+贪心。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n,last,ans;
const int N=200005;
priority_queue<int,vector<int>,greater<int> >q;
struct OPT{
int opt,val;
}o[N];
char s[5];
int main() {
scanf("%d",&n);
for(int i=1,x;i<=n;i++) {
scanf("%s%d",s,&x);
if(s[0]=='c') o[i].opt=0,o[i].val=x;
else o[i].opt=1,o[i].val=x;
}
int minn=0x3f3f3f3f,fin=0;
for(int i=n-1;i;i--)
if(o[i].opt==1)
o[i].val=min(o[i].val,minn),minn=min(minn,o[i].val);//,printf("%d ",o[i].val);
for(int i=1;i<n;i++) {
if(o[i].opt==1) {
for(int j=last+1;j<i;j++) {
if(q.size()&&q.size()==o[i].val-1) {
if(q.top()<o[j].val)
ans+=o[j].val-q.top(),q.pop(),q.push(o[j].val);
}
else if(q.size()<o[i].val-1)ans+=o[j].val,q.push(o[j].val);
}
last=i;
}
}
for(int i=last+1;i<n;i++) ans+=o[i].val;
cout<<ans<<endl;
}
T3
和数三角形差不多，但是这个评测机跑的好快啊。。。3000的n^2logn能过。。。或许是我太弱了
double判相等不是要手写==吗。。。难受
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
int n,ans;
const int N=3005;
double stk[N];int top;
bool cmp(double x,double y) {
return x<y;
}
int cnt[N],ncnt;
struct Points{int x,y;}p[N];
main() {
freopen("triangle.in","r",stdin);
freopen("triangle.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y);
for(int i=1;i<=n;i++) {
top=0;
int sz=0;
for(int j=i+1;j<=n;j++) {
if(p[i].y==p[j].y) sz++;
else stk[++top]=((p[i].x-p[j].x)*1.0/(p[i].y-p[j].y)*1.0);
}
double last=9420956464534400;ncnt=0;memset(cnt,0,sizeof cnt);
sort(stk+1,stk+1+top,cmp);
for(int j=1;j<=top;j++) {
if(stk[j]==last) cnt[ncnt]++;
else ncnt++,last=stk[j],cnt[ncnt]=1;
}
for(int j=1;j<=ncnt;j++)
if(cnt[j]>=2) ans-=(cnt[j]-1)*cnt[j]/2;
if(sz>=2) ans-=(sz)*(sz-1)/2;
}
cout<<n*(n-1)*(n-2)/6+ans;
}