2018 icpc 南京网络赛
题目：链接
A. An Olympian Math Problem
输出n-1即可(女朋友猜的)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll fac[103];
int main()
{
ll n,T;cin>>T;
while(T--)
{
cin>>n;
cout<<n-1<<endl;
}
return 0;
}B. The writing on the wall
遍历该矩形的所有右下角点；对于每一个这样的点(x, y)，假设该点作为矩形的右下角；然后，在y所在的行中找到距离x最近的一格为空的土地，并将其标记为L
则以(x, y)为右下角形成的宽度为1的矩形个数是（x−L）个；而以(x, y)为右下角形成的宽度为2的矩形个数是（x−L)(x−L−1)/2 个
从第y-1行到第y行计算其x-L方向上的最小值；接着依次计算每一列的最大值或最小值即可完成整个操作流程；实际上判断每个点的时间复杂度为10^9级……但实际运行中由于判题机性能优化等技术因素……使得程序运行时间远低于理论预期水平
也可能数据较水。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+10;
vector<int>G[maxn];
int n,m,k;
int L[maxn],iter[maxn],len[maxn];
int main()
{
int T,cas=0;scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=n;i++) G[i].clear();
while(k--)
{
int x,y;scanf("%d%d",&x,&y);
G[y].push_back(x);
}
for(int i=1;i<=m;i++)
{
len[i]=G[i].size();
sort(G[i].begin(),G[i].end());
iter[i]=0;L[i]=0;
}
ll ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(iter[j]<len[j]&&G[j][iter[j]]==i)
{
L[j]=i;iter[j]++;
}
}
for(int j=1;j<=m;j++)
{
int mi=2e9;
for(int k=j;k>=1;k--)
{
mi=min(mi,i-L[k]);
ans+=mi;
if(mi==0) break;
}
}
}
printf("Case #%d: %lld\n",++cas,ans);
}
return 0;
}E. AC Challenge
对于状压dp中的每一个状态进行合法性验证（具体而言，在判断某个状态i是否合法时,必须确保其所有依赖的状态j也在该集合内）。
若此状态合法，则用它的上一步状态来更新此状态。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=22;
ll a[maxn],b[maxn];
ll dp[1<<21];
vector<int>G[maxn];
int main()
{
for(int i=0;i<(1<<21);i++) dp[i]=-1e18;
dp[0]=0;
int n;scanf("%d",&n);
for(int i=0;i<n;i++)
{
int Q;
scanf("%lld%lld%d",&a[i],&b[i],&Q);
while(Q--)
{
int tmp;scanf("%d",&tmp);
G[i].push_back(tmp-1);
}
}
for(int s=1;s<(1<<n);s++)
{
bool bb=0;
for(int i=0;i<n;i++)
{
if(!(s>>i&1)) continue;
for(int j=0;j<G[i].size();j++)
if(!(s>>G[i][j]&1)) bb=1;
if(bb) break;
}
if(bb) continue;
for(int i=0;i<n;i++)
{
if(!(s>>i&1)) continue;
int t=0,S=s;
while(S)
{
if(S&1) t++;
S/=2;
}
dp[s]=max(dp[s],dp[s^(1<<i)]+a[i]*t+b[i]);
}
}
printf("%lld\n",dp[(1<<n)-1]);
return 0;
}G. Lpl and Energy-saving Lamps
在当前序列中，在所有满足条件的a[i]中找到最小的那个值i，在该位置处将对应的灯泡替换掉，并将其标记为无穷大。
然后灯泡数量s=s-a[i]。线段树维护即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,k,Q,s;
int a[maxn],tree[maxn<<2],ans1[maxn],ans2[maxn];
void build(int l,int r,int rt)
{
if(l==r)
{
tree[rt]=a[l];
return;
}
int mid=(l+r)/2;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}
int query(int C,int l,int r,int rt)
{
if(l==r)
{
s-=a[l];
return l;
}
int mid=(l+r)/2;
if(tree[rt<<1]<=C) return query(C,l,mid,rt<<1);
else return query(C,mid+1,r,rt<<1|1);
}
void update(int L,int l,int r,int rt)
{
if(l==r)
{
tree[rt]=2e9;
return;
}
int mid=(l+r)/2;
if(L<=mid) update(L,l,mid,rt<<1);
else update(L,mid+1,r,rt<<1|1);
tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,n,1);
s=0;
for(int i=1;i<=100000;i++)
{
s+=k;
ans1[i]=ans1[i-1];
while(s>=tree[1])
{
ans1[i]++;
int id=query(s,1,n,1);
update(id,1,n,1);
}
ans2[i]=s;
if(tree[1]==2e9)
{
for(int j=i+1;j<=100000;j++)
{
ans1[j]=ans1[i];
ans2[j]=ans2[i];
}
break;
}
}
scanf("%d",&Q);
while(Q--)
{
int t;scanf("%d",&t);
printf("%d %d\n",ans1[t],ans2[t]);
}
return 0;
}J. Sum
把每个数拆成素数相乘。
设x=(a[1]b[1])*(a[2]b[2])*(a[3]^b[3])....
其中a[i]为质数，b[i]为指数，
然后令x=n*m,
n=(a[1]b1[1])*(a[2]b1[2])*(a[3]^b1[3])...
m=(a[1]b2[1])*(a[2]b2[2])*(a[3]^b2[3])...
则有b[1]=b1[1]+b2[1],b[2]=b1[2]+b2[2],b[3]=b1[3]+b2[3]...
问题转化成有几种合法方法分配b1,b2两个数组。
对于x的所有b[i]，若存在b[i]>2，则一定无法合理安排。
因为b1[i]和b2[i]中一定有一个大于2，这样n和m至少有
一个数字含有一个完全平方数的约数。
假设b1[i]>2，则一定有n=t*a[i]^2,因此n不合法。
若b[i]=2,则只有b1[i]=1,b2[i]=1,一种选择。
若b[i]==1,则可以b1[i]=0,b2[i]=1或b1[i]=1,b2[i]=0。
代码：
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
const int maxn=20000005;
int a[maxn],b[maxn];
bool vis[maxn];
int p[maxn],q[maxn],pp[maxn];
int sum[maxn];
void init()
{
int len=0;
a[1]=1;
for(int i=2;i<maxn;i++)
{
if(!vis[i]) p[len++]=i;
for(int j=0;j<len&&1LL*i*p[j]<1LL*maxn;j++)
{
vis[i*p[j]]=1;
q[i*p[j]]=p[j];
if(i%p[j]==0) break;
}
}
sum[1]=1;
for(int i=2;i<maxn;i++)
{
if(!vis[i]) a[i]=2;
else
{
int x=i,k=0;
while(x%q[i]==0)
{
x/=q[i];k++;
if(k>2) break;
}
if(k>2) a[i]=0;
else if(k==2) a[i]=a[x];
else a[i]=2*a[x];
}
sum[i]=sum[i-1]+a[i];
}
}
int main()
{
init();
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
printf("%d\n",sum[n]);
}
return 0;
}L. Magical Girl Haze
把每个点拆成k+1个点建立分层图，对于第i个点，拆成i,i+n,i+2n...i+kn
若原图中i~j有一条权值为x的边，则
add_edge(i,j,x),add_edge(i+n,j+n,x).....add_edge(i+kn,j+kn,x)
add_edge(i,j+n,0),add_edge(i+n,j+2*n,0)....add_edge(i+(k-1)n,j+kn,0)
每向上走一层相当于走了一条权值为0的边，
假设走了(i,j+n,0)相当于从第0层走到了第一层，而把i~j这条边的权值改为0。
最后输出1~(k+1)*n的最短路即可。
代码:
#include <bits/stdc++.h>
using namespace std;
const int mn = 1400010, mm = 5000010;
const long long inf = 1e18;
int n, m, k;
int num;
int from[mm], to[mm], nx[mm], fr[mm];
long long cost[mm];
void addedge(int a, int b, long long c)
{
for (int i = 0; i <=k; i++)
{
num++;
from[num] = a + i * n;
to[num] = b + i * n;
cost[num] = c;
nx[num] = fr[a + i * n];
fr[a + i * n] = num;
}
for (int i = 0; i < k ; i++)
{
num++;
from[num] = a + i * n;
to[num] = b + (i + 1) * n;
cost[num] = 0;
nx[num] = fr[a + i * n];
fr[a + i * n] = num;
}
}
struct node
{
int id;
long long w;
friend bool operator < (struct node a, struct node b)
{
return a.w > b.w;
}
} dis[mn];
priority_queue<node>q;
void dijkstra(int a)
{
for (int i = 1; i < mn; i++)
{
dis[i].id = i;
dis[i].w = inf;
}
dis[a].w = 0;
q.push(dis[a]);
while (!q.empty())
{
node cd = q.top();
q.pop();
for (int i = fr[cd.id]; i != -1; i = nx[i])
{
int v = to[i];
if (dis[v].w > dis[cd.id].w + cost[i])
{
dis[v].w = dis[cd.id].w + cost[i];
q.push(dis[v]);
}
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
num = 0;
memset(fr, -1, sizeof fr);
scanf("%d %d %d", &n, &m, &k);
while (m--)
{
int a, b;
long long c;
scanf("%d %d %lld", &a, &b, &c);
addedge(a, b, c);
}
dijkstra(1);
printf("%lld\n", dis[k * n + n].w);
}
return 0;
}