又膜了场JSOI2015，壮烈垫底
条哥不知道去哪浪，先把题目放上了
为了比赛的公平性，我先陪神(S)犇(B)桢泼会儿隔膜
T1
看上去好像是DP，但不知道怎么转移。。
orz NiroBC AC
orz 神(S)犇(S)桢 40
正解是容斥，答案为：
三维枚举i,j,k套下公式就搞定辣。
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 405
#define P 1000000007
int n,m,t,k,l;
long long ans;
long long c[N][N],d[N][N*N];
int main(){
scanf("%d%d%d",&n,&m,&l);
for (int i=0;i<=400;i++) c[i][0]=1;
c[1][1]=1;
for (int i=1;i<=max(n,max(m,l));i++)
for (int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%P;
for (int i=1;i<=401;i++) d[i][0]=1;
for (int i=1;i<=l+1;i++)
for (int j=1;j<=n*m;j++) d[i][j]=(d[i][j-1]*i)%P;
for (int i=0;i<=n;i++)
for (int j=0;j<=m;j++)
for (int k=0;k<=l;k++){
long long s=c[n][i]*c[m][j]%P*c[l][k]%P*d[k+1][i*j]%P;
if ((n+m+l-i-j-k)%2==0) ans=(ans+s)%P;else ans=(ans-s+P)%P;
}
printf("%lld\n",ans);
}
T2
这是一道水题（好吧其实是以前做过）
维护一个队列，里面存前面产生的gcd及产生该gcd的最左端。
易得队列有单调性，简单维护即可。
理论复杂度为n2，但实际复杂度较小（有很多gcd重复）。
然而。。有个变量没开long long然后滚粗了。。
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1001000
long long a[N],b[N],c[N];
int n,m,t;
long long k,l,s,ans;
long long gcd(long long a,long long b){
if (a%b) return(gcd(b,a%b));
else return(b);
}
int main(){
// freopen("gcd.in","r",stdin);
// freopen("gcd.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
for (int i=1;i<=n;i++){
t=m;
m=0;
for (int j=1;j<=t;j++){
k=gcd(b[j],a[i]);
if (k!=b[m]){
b[++m]=k;
c[m]=c[j];
ans=max(ans,b[m]*(i-c[m]+1));
}
}
if (b[m]!=a[i]){
b[++m]=a[i];
c[m]=i;
ans=max(ans,a[i]);
}
}
printf("%lld\n",ans);
}
T3
一道十分复杂的题目（好吧其实是我懒。。）
首先对每条路径经过点新开一个点，上站的边权为1，下站和中途乘坐边权为0。
然后跑一遍最短路就求出第一问辣（SPFA会被卡飞，只能用堆优化dijkstra)。
然后处理出所有可能经过的点建新图（可以保证是有向无环图）。
按拓扑序求出最长距离就可以辣。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define a first
#define b second
#define N 100100
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int M=5000010;
const int inf=2000000000;
pair<ull,int>a[M];
int n,m,y,t,st,ed,tmp,cnt,num,Num;
char s[50];
int head[M],vet[M],next[M],Head[M],Vet[M],Next[M],cost[M],init[M],dis[M],Dis[M],len[M][2],flag[M],x[M],q[M];
priority_queue<PII,vector<PII>,greater<PII> >Q;
int shit(){
ull w=0;
for (int i=0;i<strlen(s);i++) w=w*233+s[i];
return(w);
}
int solve(){
ull ss=shit();
int ans=a[lower_bound(a+1,a+n+1,make_pair(ss,0))-a].b;
return(ans);
}
void add(int a,int b,int c,int d){
next[++num]=head[a];
head[a]=num;
vet[num]=b;
len[num][0]=c;
len[num][1]=d;
}
void Add(int a,int b,int c){
Next[++Num]=Head[a];
Head[a]=Num;
Vet[Num]=b;
cost[Num]=c;
init[b]++;
}
int main(){
scanf("%d%d",&m,&n);
for (int i=1;i<=n;i++){
scanf("%s",s);
for (int j=0;j<strlen(s);j++)a[i].a=shit();
a[i].b=i;
}
sort(a+1,a+n+1);
cnt=n;
for (int i=1;i<=m;i++){
scanf("%d",&t);
scanf("%s",s);
x[1]=solve();
add(x[1],++cnt,1,0);
for (int j=2;j<=t;j++){
scanf("%s",s);
y=cnt,x[j]=solve();
add(y,++cnt,0,1);
add(x[j],cnt,1,0);
add(cnt,x[j],0,0);
}
add(x[t],++cnt,1,0);
for (int j=t-1;j>=1;j--){
y=cnt;
add(y,++cnt,0,1);
add(x[j],cnt,1,0);
add(cnt,x[j],0,0);
}
}
scanf("%s",s);
st=solve();
scanf("%s",s);
ed=solve();
for (int i=1;i<=cnt;i++) dis[i]=inf;
for (int i=1;i<=cnt;i++) flag[i]=0;
Q.push(make_pair(0,st));dis[st]=0;
while (!Q.empty()){
int u=Q.top().b;Q.pop();
if (flag[u])continue;
flag[u]=1;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (dis[u]+len[e][0]<dis[v]){
dis[v]=dis[u]+len[e][0];
Q.push(make_pair(dis[v],v));
}
}
}
for (int i=1;i<=cnt;i++)
for (int e=head[i];e;e=next[e]){
if (dis[i]+len[e][0]==dis[vet[e]]) Add(i,vet[e],len[e][1]);
}
int pre=1,tail=0;
for (int i=1;i<=cnt;i++) if (init[i]==0) q[++tail]=i;
while (pre<=tail){
int u=q[pre++];
for (int e=Head[u];e;e=Next[e]){
int v=Vet[e];
Dis[v]=max(Dis[v],Dis[u]+cost[e]);
if ((--init[v])==0) q[++tail]=v;
}
}
printf("%d\n",dis[ed]);
printf("%d\n",Dis[ed]);
}
评论 (0)
