写在前面
今天的题是去年考过的，(cb)依旧很垃圾(QAQ)。
T1 求和
Idea
前缀和
我们先将左上角的点看作((1,1)),右下角的点看作((n,m))，那么有(displaystyle sum_{i=1}^{n} sum_{j=1}^{m} d[i][j] = frac{m imes n imes (n+m)}{2})，自己手推下。就有了
证明如下
[ ext{n行}egin{matrix}underbrace{ left{ egin{matrix}1&2&3&cdots&1+n-1\2&3&4&cdots&2+n-1\vdots&&&&vdots\n&n+1&n+2&cdots&m+n-1end{matrix}
ight. }\ ext{m项}end{matrix}
]
可以发现 每一行都是等差数列，求和，相加(Ans=displaystyle frac{m imes n imes (n+m)}{2})
那么(Ans)就是前缀和中的问题。
(Ans=sum[x_2][y_2]+sum[x_1-1][y_1-1]-sum[x_1][y_2]-sum[x_2][y_1-1])
但是计算乘法时会爆(long;long)，可以用高精，也可以用龟速乘(好像是个这名)
单纯的计算好像有(70;pts).
Code
int x1,y,x2,y2,m;
inline int mul(int n, int m, int p){
int a=n,ans=0;
for(;m;m>>=1){
if(m&1) ans=(ans+a)%p;
a=(a*2)%p;
}
return ans;
}
inline int power(int x,int y,int m){
int sum=x+y;
if(~x&1) x>>=1;
else if(~y&1) y>>=1;
else sum>>=1;
return mul(mul(x,y,m),sum,m);
}
signed main(){
freopen(File".in","r",stdin);
freopen(File".out","w",stdout);
x1=read(); y=read();
x2=read(); y2=read(); m=read();
printf("%lld",(power(x2,y2,m)-power(x1-1,y2,m)-power(x2,y-1,m)+power(x1-1,y-1,m)+2*m)%m);
return 0;
}
T2 分组配对
Idea
先打了个暴力,发现大样例过不了。
然后想到了二分，又想暴力加区间会炸掉，于是又用了倍增。
关键是二分，我瞎调了调居然过了，
复杂度为(O(n log^2 n))，应该是吧。。。
Code
int a[maxn],b[maxn];
int aa[maxn],bb[maxn];
int n,M;
inline bool check(int x,int len){//判断为是否合法区间
int y=x+len-1;
for(int i=x;i<=y;i++) aa[i]=a[i],bb[i]=b[i];
sort(aa+x,aa+y+1); sort(bb+x,bb+y+1);
int res=0;
for(int i=x;i<=y;i++) res+=aa[i]*bb[i];
return res<=M;
}
inline int solve(){
int QAQ=0,qwq=1;//请忽略，不知该起什么变量名
while(qwq<=n){
int len=1;
for(;check(qwq,len)&&qwq+len-1<=n;len*=2);//倍增
int l=len>>1,r=min(len-1,qwq+len-1);
while(l<r){//二分
int mid=(l+r+1)>>1;
if(check(qwq,mid)) l=mid;
else r=mid-1;
}
qwq+=l; QAQ++;
}
return QAQ;
}
signed main(){
freopen(File".in","r",stdin);
freopen(File".out","w",stdout);
n=read(); M=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
printf("%d",solve());
return 0;
}
T3 城市游戏
Idea
蒟蒻不会删边
，于是只输出了(-1)，(QAQ)
但好像有(15;pts)，真良心。
听(Blng)讲的时候说这是一棵 最短路径树,我到现在还没有学会(T\_T)
先放上有注释的(Code)
Code
const int M=450000,N=120000;
typedef long long ll;
const ll inf=1000000000000000LL;
struct node
{
int a,b,jl;ll l;
bool operator <(const node &no) const
{return l<no.l;}
};
node e[M],a[M];
int fi[N],ne[M],dep[N],fa[N],father[N];
ll pr[N],d[N],dp[N];
int p=0,pE=0,cnt=0,i,n,m,aa,bb,t;
priority_queue<pair<ll,int> >q;
int getf(int x){if (fa[x]==x) return x;fa[x]=getf(fa[x]);return fa[x];}
void addE(int aa,int bb,ll l){pE++;e[pE].a=aa;e[pE].b=bb; e[pE].l=l;e[pE].jl=0;ne[pE]=fi[aa];fi[aa]=pE;}
void addA(int aa,int bb,ll l){p++;a[p].a=aa;a[p].b=bb;a[p].l=l;}
//两次建边
void dfs(int x)
{
for(int j=fi[x];j;j=ne[j])
if(e[j].jl==1)
{
if(dep[e[j].b]==-1)
{
dep[e[j].b]=dep[x]+1;
d[e[j].b]=d[x]+e[j].l;
father[e[j].b]=x;//从n到这个点的最短路径经过的倒数第二个点是谁。
dfs(e[j].b);
}
else e[j].jl=0;//删去的y到x的边，但是不会删去x到y的边
}
}
//把边权搞到根节点n上 ，这里是处理出来d[i]和最短路上两点的关系
void dfs2(int x)
{
for(int j=fi[x];j;j=ne[j])
{
int y=e[j].b,z=e[i].l;
if (e[j].jl==0&&y>x&&y!=father[x])//判断是否是在最短路上的倒数第二个点
addA(x,y,d[x]+d[y]+z);//每个点与自己记录的倒数第二个点连边，边的长度为在原图中这两个点之间的边的长度
}
for(int j=fi[x];j;j=ne[j]) if (e[j].jl==1) dfs2(e[j].b);//沿着整个边进行建树
}
//构建最短路径树
int main()
{
// freopen("city.in","r",stdin);
// freopen("city.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
int u,v,l;
scanf("%d%d%d",&u,&v,&l);
addE(u,v,l),addE(v,u,l);
}
//以n为源点最短路
for(i=1;i<=n;i++) d[i]=inf; d[n]=0;
q.push(make_pair(0,n));
while (!q.empty())
{
if (-d[q.top().second]!=q.top().first) {q.pop();continue;}
int u=q.top().second;q.pop();
for (int j=fi[u];j>0;j=ne[j])
if (d[u]+e[j].l<d[e[j].b])
{
d[e[j].b]=d[u]+e[j].l;
q.push(make_pair(-d[e[j].b],e[j].b));
}
}
//构建最短路树
for (int j=1;j<=pE;j++) if(d[e[j].b]==d[e[j].a]+e[j].l) e[j].jl=1;
//标记最短路的边
memset(dep,-1,sizeof(dep)); dep[n]=0;dfs(n); dfs2(n);
//处理n与各个节点的关系以及d[i]
//图，，，，
//路径长度是dis[b]+L(a,b)+(dist[a]-dist[v])=(dist[a]+dist[b]+L(a,b))-dist[v]
//把前面单独取出来
//枚举删边
sort(a+1,a+1+p);
//算贪心 ，要按顺序把a-b链上的点的pr[]都搞出来，就是利用这个，所以要在这条链上跳。
//在搞pr的时候就相当于并查集了。。也就很像所谓的kruskal了。。
for(i=1;i<=n;i++) fa[i]=i; for(i=1;i<=n;i++) pr[i]=inf;//存的是取出式子
for(i=1;i<=p;i++)
{
int u=getf(a[i].a),v=getf(a[i].b);
while (u!=v)
{
if (dep[u]<dep[v]) swap(u,v);
pr[u]=a[i].l-d[u]; cnt++;//这点枚举删边
fa[u]=getf(father[u]); u=fa[u];
}
if (cnt>=n-1) break;
}
//所以我们再跑一遍最短路的目的就是综合上面的情况。。
for (i=1;i<=n;i++) dp[i]=inf;
dp[n]=0;q.push(make_pair(0,n));
while(!q.empty())
{
if (-dp[q.top().second]!=q.top().first) {q.pop();continue;}
int u=q.top().second;q.pop();
for (int j=fi[u];j;j=ne[j])
{
int v=e[j].b;
ll ret=dp[u]+e[j].l;
if (e[j].jl) ret=max(ret,pr[v]);//另一种就是割掉一条边所产生的pr[]。
else ret=max(ret,d[v]);//一种就是直接在树上就有的最短路上的点，那么它对于答案的贡献就是d【】
if(ret<dp[v]) dp[v]=ret,q.push(make_pair(-dp[v],v));
}
}
if(dp[1]==inf) cout<<-1<<endl;
else cout<<dp[1]<<endl;//答案就是dp[1]了
return 0;
}
[The quad End
]
[ ext{楼台上戏子和衣吟唱，一曲画堂春；不如就携手隐没红尘，相对忘贫生-《画堂春》}
]