最近做的BZOJ题目 I
因为有一些题目难度不是很大，网上也能够搜到题解，单独拿出来讲也没有什么意思，所以就在这里稍稍记录一下，不另写博文了，而且，从标题可以看出来，这将会是一系列的博文。
36
Updata：这里一共记录了36道题目的简单题解，感觉也差不多了，而且，36是个好数字，我就不破坏它了。所以这一篇到这里就结束吧，敬请期待Ⅱ。
BZOJ 1191 二分图匹配水题，匈牙利算法直接过。
BZOJ 2326 矩阵乘法+数学分类讨论。
BZOJ 1271 二分答案。
BZOJ 1196 这题以前用贪心水过，直到今天才发现，我的贪心是有问题的，是可以被卡掉的，这题应该二分答案。
BZOJ 1211 和明明的烦恼差不多，只是需要分解质因数，否则乘起来会爆掉long long。本来想打python的，后来发现似乎有点麻烦……
BZOJ 3674 这题是3673的加强版，3673的骗分办法就懒得讲了，随便YY一下就可以了。而且，反正只要把这题AC了，3673也就顺便AC了（双倍经验），用主席树维护可持久化数组，结果出了问题，但是自己电脑上怎么也拍不出来，后来照着Claris的程序改，发现是因为路径压缩的时候，直接在树上的节点上改了，没有另外地用change()改一下，结果就是，改了的结点可能是很久以前某次操作后留下来的结点……
BZOJ 1257 我最讨厌的数学题，不过这道题目也算是简单的了，并非数论神题。首先，通过打表可以发现，对于一个i，当[tex]t=\frac{n}{i} \rightarrow (\frac{n}{i+1} +1)[/tex]时，n%t的值都是递增的，根据这个规律，所有小于[tex]\sqrt{n}[/tex]的数都可以暴力求出n%i，接着再对于[tex]i=1 \rightarrow \sqrt{n}[/tex]用等差数列求和的办法求出，要注意的是必须要long long，还有一些细节对拍一下就行了。
BZOJ 2729 组合数学题，有点坑。开始的时候直接插空法，一直都AC不了，"98 2"的数据就将我的程序卡掉了，后来才明白有一种特殊情况没有考虑、假设，男生先全都站好，那么就有n!种站法，接着将两个老师插入进去，有A(n+1,2)种站法，最后将女生们插入进去，有A(n+3,m)种站法，乘起来就是答案，但是，这种考虑忽略了一种情况，两个老师可能是被女生给隔开的，也就是说，两个老师可以站在一起，在将女生插入进去的时候，有一个女生将老师给隔开了（因为两个女生不能相邻，所以将老师隔开的只能是一个女生），这样就有m*2种站法（老师的先后位置也要考虑），然后再将这个当成一组，插入到男生中，最后再将剩余的女生插入到队伍中。总的答案=n!*(A(n+1,2)*A(n+3,m)+m*2*(n+1)*A(n+2,m-1))。懒得打高精度了，直接用了python。
BZOJ 1858 线段树水题，结果还是调了很久TAT，不过样例过了就一遍AC了。
BZOJ 1059 二分图匹配，因为扒了模板，所以有些冗长。
BZOJ 3083 树链剖分+线段树+dfs序，开始的时候假设1为根dfs并建树。真实的根可能会发生变化，所以需要考虑根所在的位置，如果根在查询的结点x的子树中，则找到根到x路径上离x最近的那个结点y，查询的时候就查询整棵树中除了y的子树的那一部分；当根不再x的子树中时，就直接查询x的子树。
BZOJ 1412 最小割，源点往狼连边，容量无限，羊往汇点连边，容量无限，狼往所有非狼格子连边，容量为1，空地往所有非狼连边，容量为1。很久以前在vijos上做过，结果由于莫名其妙的原因，一直没有AC……
BZOJ 1067 离散化+线段树，要考虑的情况比较多，所以就不一一罗列了，具体的可以看程序，其次，这道题目在vijos上也是有的，但是，如果对于x==y的情况（虽然题面上说保证这种数据不存在）不考虑的话，会各种WA的，而且，如果x==y时，当年的降雨量不知道，必须要输出maybe而不能输出true……
BZOJ 3155 本题BZOJ上的题面是错误的，大致的题意是这样的，设Si一个数列a1,a2,...an前i个数的和，那么对于给定的数列{an}，就会有一个对应的数列{Sn}，现在需要进行两种操作：1.修改ai的值为x 2.查询{Sn}中前i个数的和。树状数组维护一下就行了，很简单。
BZOJ 3064 线段树区间更新，要打四个标记，分类讨论一下就行了。还有，刚发现我的读优模板出了个小错误，读负数的时候会有点问题，不过之前的程序都懒得改了，大家注意一下。
BZOJ 1911 斜率优化DP。果然，DP永远都是我的弱项，虽然一眼就看出来是斜率优化DP，但是，还是卡了好久，于是上网搜了一篇有关斜率优化的文章，结果发现自己公式化简的时候完全搞错了TAT……
BZOJ 1024 直接暴搜就行了
BZOJ 1029 贪心，开始的时候还以为是DP，结果推到死都推不出结果来，后来去百度了一下题解才知道原来是贪心，果然我还是太弱了吗……
BZOJ 1096 斜率优化DP，开始的时候以为是简单的单调队列优化DP，结果怎么调都调不出来，然后Claris一语道破天机，我才知道是斜率优化DP，稍稍推了一下公式就做出来了
BZOJ 1207 特殊版的LIS，还是[tex]O(n^2)[/tex]的，不过还是卡过去了。
BZOJ 1452 二维树状数组，本来打的是二维线段树，结果MLE，把数组开小一点后RE了，然后以为二维线段树不可做就改打了二维树状数组，结果也各种RE，后来才发现原来主程序的一个地方打错了……
BZOJ 1922 有特殊要求的最短路，按照题目要求搞就好了，开始的时候打了Dijkstra，结果怎么也调不出来……后来改打SPFA，也怎么也调不出来……直到最后，我才看到题目里面说，所有边都是单向边……
BZOJ 1968 数学题，开始的时候还打了筛法，在自己电脑上是过去了，BZ上也卡过去了（BZ上这题的时间限制竟然只有1s），后来才知道原来根本不用求素数，直接暴力就行了……
BZOJ 2818 也是数学题，先线性筛求出[tex]\varphi(x)[/tex]函数，然后枚举每个素数就行了。
BZOJ 1045 想了好久，最后YY出了一种错误的做法，算出来的值比答案要小。然后就直接去网上搜题解了，后面是我看的题解的链接：http://www.cnblogs.com/JS-Shining/archive/2012/09/24/2700711.html
BZOJ 1821 二分答案+并查集。
BZOJ 2190 欧拉函数。忽然发现，我的欧拉函数的模板好像不是线性筛的，而是爱氏筛，线性筛都不会打了……不过暂时也懒得回顾了，就先这样吧。
BZOJ 2631 LCT裸题，不知道为什么，这一次的LCT打的特别萎，速度很慢，好在还是跑出来了。
BZOJ 2243 树链剖分。
BZOJ 1854 二分图匹配，和HNOI的那道超级英雄差不多，唯一要注意的是，数据比较大，所以跑匈牙利算法的时候要用时间戳，不然会超时。
BZOJ 1037 四维DP。开始以为是三维DP，结果连样例都过不了，后来转成四维DP，因为状态出了问题，本来打算f[i][j][k][l]表示前i位，有j个男孩纸，右端点为i的某一段中，男孩纸和女孩纸数目之差为k（所以会有负数），最后一共有连续l个相同的孩纸（l为正表示男孩纸，为负表示女孩纸），结果惨遭WA，而且，MLE了（开了两亿多数组，在BZOJ 上Compiling了一分钟左右，话说我真得不是故意的）后来才发现这样搞不好，然后去网上搜了一下，变成了右端点为i的某段中男孩纸最多比女孩纸多了k个，女孩纸最多比男孩纸多了l个，然后稍稍改一下转移方程就AC了。
BZOJ 1877 拆点费用流，结果TLE了好久，后来胡乱地将源点s和汇点t的变量名从小写改成大写然后就AC了……
BZOJ 1103 树链剖分。
BZOJ 1216 我果然还是太弱了，这么水的模拟题都做了这么久，一直出错，直到今天头脑稍稍清醒了一点，终于做出来了。
BZOJ 1293 离散化后再扫一遍就行了。
BZOJ 3824 简单的状压DP。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10010;
int n,m,belong[N];
int g[N],to[N],nxt[N],tot;
bool v[N];
void addedge(int x,int y) {
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
}
bool match(int x) {
for (int k=g[x];k;k=nxt[k]) {
if (v[to[k]]) continue;
v[to[k]]=true;
if (!belong[to[k]]||match(belong[to[k]])) {
belong[to[k]]=x;
return 1;
}
}
return 0;
}
int main() {
int i,x,y;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
addedge(i,x);
addedge(i,y);
}
for (i=1;i<=n;i++) {
memset(v,0,sizeof(v));
if (!match(i)) break;
}
printf("%d\n",i-1);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const D eps=1e-6;
const D pi=acos(-1.0);
int mod;
ll n,ans,t[30],r[30];
ll g[5][5],f[5],e[5],h[5][5];
void power1() {
int i,j,k;
for (i=1;i<=3;i++) for (j=1;j<=3;j++) h[i][j]=0;
for (k=1;k<=3;k++) for (i=1;i<=3;i++) for (j=1;j<=3;j++) (h[i][j]+=(g[i][k]*g[k][j])%mod)%=mod;
for (i=1;i<=3;i++) for (j=1;j<=3;j++) g[i][j]=h[i][j];
}
void power2() {
int i,j;
for (i=1;i<=3;i++) e[i]=0;
for (i=1;i<=3;i++) for (j=1;j<=3;j++) (e[i]+=(g[i][j]*f[j])%mod)%=mod;
for (i=1;i<=3;i++) f[i]=e[i];
}
ll calc(ll x,int y,ll b) {
f[1]=x; f[2]=(r[y]-1)%mod; f[3]=1;
g[1][1]=r[y+1]%mod; g[1][2]=1; g[1][3]=1;
g[2][1]=0; g[2][2]=1; g[2][3]=1;
g[3][1]=g[3][2]=0; g[3][3]=1;
for (;b;b>>=1LL) {
if (b&1LL) power2();
power1();
}
return f[1]%mod;
}
int main() {
int i;
cin>>n>>mod;
for (t[0]=9,i=1;i<=18;i++) t[i]=t[i-1]*10;
for (r[0]=1,i=1;i<=18;i++) r[i]=r[i-1]*10;
for (i=0;i<18;i++) {
if (t[i]<=n) {
ans=calc(ans,i,t[i]);
n-=t[i];
} else {
ans=calc(ans,i,n);
break;
}
}
cout<<ans<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=200010;
struct node{int l,r,d;}b[N];
int T,n,sum,ans;
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
bool check(int l,int r) {
sum=0; int i,t;
for (i=1;i<=n;i++) {
if (b[i].r<l||b[i].l>r) continue;
sum+=(min(b[i].r,r)-b[i].l)/b[i].d+1;
if (b[i].l<l) sum-=(l-b[i].l-1)/b[i].d+1;
} return sum&1;
}
int solve(int l,int r) {
if (l==r) return check(l,r)?l:-1;
int mid=((ll)l+(ll)r)>>1ll;
return check(l,mid)?solve(l,mid):solve(mid+1,r);
}
int main() {
int i,ans; read(T);
while (T--) {
for (read(n),i=1;i<=n;i++) read(b[i].l),read(b[i].r),read(b[i].d);
ans=solve(0,infi);
if (ans>=0) printf("%d %d\n",ans,sum);
else puts("Poor QIN Teng:(");
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=20010;
struct node{int x,y,z;}a[N],b[N];
int n,m,k,fa[N];
bool cmp(const node &a,const node &b) {return a.z<b.z;}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
bool check(int cost) {
int i,tot=0,block=n,fx,fy;
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<m;i++) {
if (a[i].z>cost) break;
fx=find(a[i].x);
fy=find(a[i].y);
if (fx==fy) continue;
fa[fx]=fy; block--; tot++;
} if (tot<k) return 0;
for (i=1;i<m;i++) {
if (b[i].z>cost) break;
fx=find(b[i].x);
fy=find(b[i].y);
if (fx==fy) continue;
fa[fx]=fy; block--;
} return block==1;
}
int main() {
int i,l=1,r=30000,mid;
read(n); read(k); read(m);
for (i=1;i<m;i++) {
read(a[i].x); read(a[i].y); read(a[i].z);
b[i].x=a[i].x; b[i].y=a[i].y; read(b[i].z);
}
sort(a+1,a+m,cmp);
sort(b+1,b+m,cmp);
while (l<r) {
mid=(l+r)>>1;
if (check(mid)) r=mid;
else l=mid+1;
} printf("%d\n",l);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=200;
int n,d[N],sum,p[N],num[N],tot;
bool b[N],ok;
ll ans;
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void calc(int n,int k) {
int i,j,x;
for (i=1;i<=n;i++)
for (j=2,x=i;j<=i;j++)
while (x%j==0) x/=j,num[j]+=k;
}
int main() {
int i,j,x;
for (read(n),i=1;i<=n;i++) {
read(d[i]); d[i]--; sum+=d[i];
}
if (sum!=n-2) return puts("0"),0;
if (n==1) return puts("1"),0;
calc(sum,1);
for (i=1;i<=n;i++) {
if (d[i]<0) return puts("0"),0;
if (!d[i]) continue;
calc(d[i],-1);
}
for (ans=i=1;i<=n;i++) if (num[i])
while (num[i]>0) ans*=(ll)i,num[i]--;
cout<<ans<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10000100;
int n,m,len,head[200100];
int son[N][2],fa[N],lastans;
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
int build(int l,int r) {
int t=++len,mid=(l+r)>>1;
if (l==r) {
fa[t]=l;
return t;
}
son[t][0]=build(l,mid);
son[t][1]=build(mid+1,r);
return t;
}
int ask(int i,int l,int r,int x) {
if (l==r) return fa[i];
int mid=(l+r)>>1;
return x<=mid?ask(son[i][0],l,mid,x):ask(son[i][1],mid+1,r,x);
}
int change(int i,int l,int r,int x,int y) {
int t=++len,mid=(l+r)>>1;
if (l==r) {
fa[t]=y;
return t;
}
if (x<=mid) son[t][0]=change(son[i][0],l,mid,x,y),son[t][1]=son[i][1];
else son[t][1]=change(son[i][1],mid+1,r,x,y),son[t][0]=son[i][0];
return t;
}
int find(int x,int k) {
int t=ask(head[k],1,n,x);
if (t==x) return t;
else return head[k]=change(head[k],1,n,x,t=find(t,k)),t;
}
int main() {
int i,k,x,y,fx,fy;
read(n); read(m);
head[0]=build(1,n);
for (i=1;i<=m;i++) {
head[i]=head[i-1];
read(k); read(x); x^=lastans;
if (k==2) head[i]=head[x];
else read(y),y^=lastans;
if (k==1) {
fx=find(x,i); fy=find(y,i);
if (fx!=fy) head[i]=change(head[i],1,n,fx,fy);
} else if (k==3) {
fx=find(x,i); fy=find(y,i);
printf("%d\n",lastans=(fx==fy));
}
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
ll k,n,i,l,r;
ll ans;
int main() {
cin>>k>>n;
if (k>n) ans=(k-n)*n;
for (i=1;i*i<=n&&i<=k;i++) ans+=n%i;
for (i=1;i*i<=n;i++) {
l=n/(i+1)+1; r=n/i;
if (l*l<=n) break;
if (l>k) continue;
r=min(r,k);
ans+=(ll)(n%l+n%r)*(r-l+1)/2;
} cout<<ans<<endl;
return 0;
}
def A(n,m):
if (m>n):return 0
ans=1
for i in range(m):
ans=ans*(n-i)
return ans
def multi(x):
ans=1
for i in range(x):
ans=ans*(i+1)
return ans
n,m=map(int,raw_input().split())
ans=multi(n)*A(n+1,2)*A(n+3,m)
ans=ans+multi(n)*m*(n+1)*A(n+2,m-1)*2
print ans
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=500010;
int n,m,t,num[N][2],len[N],lazy[N];
int lenl[N][2],lenr[N][2],ma[N][2];
int sumr,ans;
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void Max(int &x,int y) {if (x<y) x=y;}
void updata(int i,int k) {
num[i][k]=num[i<<1][k]+num[i<<1|1][k];
lenl[i][k]=lenl[i<<1][k];
if (lenl[i<<1][k]==len[i<<1]) Max(lenl[i][k],len[i<<1]+lenl[i<<1|1][k]);
lenr[i][k]=lenr[i<<1|1][k];
if (lenr[i<<1|1][k]==len[i<<1|1]) Max(lenr[i][k],len[i<<1|1]+lenr[i<<1][k]);
ma[i][k]=lenr[i<<1][k]+lenl[i<<1|1][k];
Max(ma[i][k],ma[i<<1][k]);
Max(ma[i][k],ma[i<<1|1][k]);
}
void build(int i,int l,int r) {
len[i]=r-l+1; lazy[i]=-1;
if (l==r) {
read(t); num[i][t]=1;
lenl[i][t]=lenr[i][t]=ma[i][t]=1;
return;
} int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
updata(i,0); updata(i,1);
}
void add(int i,int k) {
if (lazy[i]==-1) lazy[i]=k;
else if (k<2) lazy[i]=k;
else if (lazy[i]>-1&&lazy[i]<2) lazy[i]^=1;
else if (lazy[i]==2) lazy[i]=-1;
}
void clean(int i) {
if (!i) return;
if (lazy[i]>-1) {
if (lazy[i]<2) {
num[i][lazy[i]]=len[i];
lenl[i][lazy[i]]=len[i];
lenr[i][lazy[i]]=len[i];
ma[i][lazy[i]]=len[i];
num[i][lazy[i]^1]=0;
lenl[i][lazy[i]^1]=0;
lenr[i][lazy[i]^1]=0;
ma[i][lazy[i]^1]=0;
} else {
swap(num[i][0],num[i][1]);
swap(lenl[i][0],lenl[i][1]);
swap(lenr[i][0],lenr[i][1]);
swap(ma[i][0],ma[i][1]);
}
add(i<<1,lazy[i]);
add(i<<1|1,lazy[i]);
lazy[i]=-1;
}
}
void modify(int i,int l,int r,int x,int y,int z) {
clean(i);
if (x<=l&&y>=r) {
lazy[i]=z;
clean(i);
return;
} int mid=(l+r)>>1;
if (x<=mid) modify(i<<1,l,mid,x,y,z);
if (y>mid) modify(i<<1|1,mid+1,r,x,y,z);
clean(i<<1); clean(i<<1|1);
updata(i,0);
updata(i,1);
}
int ask(int i,int l,int r,int x,int y) {
clean(i);
if (x<=l&&y>=r) return num[i][1];
int mid=(l+r)>>1,ans=0;
if (x<=mid) ans+=ask(i<<1,l,mid,x,y);
if (y>mid) ans+=ask(i<<1|1,mid+1,r,x,y);
return ans;
}
void get(int i,int l,int r,int x,int y) {
clean(i);
if (x<=l&&y>=r) {
Max(ans,ma[i][1]);
Max(ans,sumr+lenl[i][1]);
if (lenr[i][1]==len[i]) sumr+=len[i];
else sumr=lenr[i][1];
return;
} int mid=(l+r)>>1;
if (x<=mid) get(i<<1,l,mid,x,y);
if (y>mid) get(i<<1|1,mid+1,r,x,y);
}
int query(int l,int r,int x,int y) {
ans=sumr=0; get(1,l,r,x,y);
return ans;
}
void print(int i,int l,int r) {
clean(i);
if (l==r) {
printf("%d ",num[i][1]);
return;
} int mid=(l+r)>>1;
print(i<<1,l,mid);
print(i<<1|1,mid+1,r);
}
int main() {
int i,k,x,y;
read(n); read(m);
build(1,0,n-1);
for (i=1;i<=m;i++) {
read(k); read(x); read(y);
if (k==0) modify(1,0,n-1,x,y,0);
else if (k==1) modify(1,0,n-1,x,y,1);
else if (k==2) modify(1,0,n-1,x,y,2);
else if (k==3) printf("%d\n",ask(1,0,n-1,x,y));
else if (k==4) printf("%d\n",query(0,n-1,x,y));
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
int T,n;
int g[210],to[N],nxt[N],tot;
int h[210],pt[N],lik[N],cnt;
int belong[210];
bool v[210],ans;
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
void addedge(int x,int y) {
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
pt[++cnt]=x; lik[cnt]=h[y]; h[y]=cnt;
}
bool find1(int x){
for (int k=g[x];k;k=nxt[k]){
if (!v[to[k]]) {
v[to[k]]=1;
if (!belong[to[k]]||find1(belong[to[k]])) {
belong[to[k]]=x;
return 1;
}
}
}
return 0;
}
bool find2(int x){
for (int k=h[x];k;k=lik[k]){
if (!v[pt[k]]) {
v[pt[k]]=1;
if (!belong[pt[k]]||find2(belong[pt[k]])) {
belong[pt[k]]=x;
return 1;
}
}
}
return 0;
}
int main() {
int i,j,x;
read(T);
while (T--) {
read(n); tot=cnt=0;
for (i=1;i<=n;i++) g[i]=h[i]=0;
for (i=1;i<=n;i++) {
for (j=1;j<=n;j++) {
read(x);
if (x==1) addedge(i,j);
}
} ans=true;
memset(belong,0,sizeof(belong));
for (i=1;i<=n;i++) {
memset(v,0,sizeof(v));
if (!find1(i)) {
ans=false;
break;
}
}
if (ans) {
memset(belong,0,sizeof(belong));
for (i=1;i<=n;i++) {
memset(v,0,sizeof(v));
if (!find2(i)) {
ans=false;
break;
}
}
}
if (ans) puts("Yes");
else puts("No");
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=200010;
int n,m,root;
int fa[N],v[N],mi[N<<1],lazy[N<<1];
int pos[N],dfn[N],ed[N],df;
int d[N],top[N],son[N],num[N];
int g[N],to[N],nxt[N],tot;
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
void Min(int &x,int y) {if (x>y) x=y;}
void addedge(int x,int y) {
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void dfs1(int x,int fat) {
fa[x]=fat;
for (int k=g[x];k;k=nxt[k]) {
if (to[k]==fat) continue;
dfs1(to[k],x);
if (num[to[k]]>num[son[x]]) son[x]=to[k];
num[x]+=num[to[k]];
} num[x]++;
}
void dfs2(int x,int t,int dep) {
dfn[x]=++df; pos[df]=x;
top[x]=t; d[x]=dep;
if (son[x]) dfs2(son[x],t,dep+1);
for (int k=g[x];k;k=nxt[k]) {
if (to[k]==fa[x]||to[k]==son[x]) continue;
dfs2(to[k],to[k],dep+1);
} ed[x]=df;
}
void build(int i,int l,int r) {
if (l==r) {
mi[i]=v[pos[l]];
return;
} int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
mi[i]=min(mi[i<<1],mi[i<<1|1]);
}
void clean(int i,int l,int r) {
if (!i) return;
if (lazy[i]) {
mi[i]=lazy[i];
if (l!=r) lazy[i<<1]=lazy[i<<1|1]=lazy[i];
lazy[i]=0;
}
}
void change(int i,int l,int r,int x,int y,int z) {
clean(i,l,r);
if (x<=l&&y>=r) {
lazy[i]=z;
clean(i,l,r);
return;
} int mid=(l+r)>>1;
if (x<=mid) change(i<<1,l,mid,x,y,z);
if (y>mid) change(i<<1|1,mid+1,r,x,y,z);
clean(i<<1,l,mid); clean(i<<1|1,mid+1,r);
mi[i]=min(mi[i<<1],mi[i<<1|1]);
return;
}
void modify(int x,int y,int z) {
while (top[x]!=top[y]) {
if (d[top[x]]<d[top[y]]) change(1,1,n,dfn[top[y]],dfn[y],z),y=fa[top[y]];
else change(1,1,n,dfn[top[x]],dfn[x],z),x=fa[top[x]];
}
if (d[x]<d[y]) change(1,1,n,dfn[x],dfn[y],z);
else change(1,1,n,dfn[y],dfn[x],z);
}
int ask(int i,int l,int r,int x,int y) {
if (x>y) return infi;
clean(i,l,r);
if (x<=l&&y>=r) return mi[i];
int mid=(l+r)>>1,ans=infi;
if (x<=mid) Min(ans,ask(i<<1,l,mid,x,y));
if (y>mid) Min(ans,ask(i<<1|1,mid+1,r,x,y));
return ans;
}
int get(int x,int y) {
int last=y;
for (;top[y]!=top[x];last=top[y],y=fa[top[y]]);
return y==x?last:son[x];
}
int query(int x) {
if (x==root) return ask(1,1,n,1,n);
else if (dfn[x]<=dfn[root]&&ed[x]>=dfn[root]) {
int t=get(x,root),ans=infi;
Min(ans,ask(1,1,n,1,dfn[t]-1));
Min(ans,ask(1,1,n,ed[t]+1,n));
return ans;
} else return ask(1,1,n,dfn[x],ed[x]);
}
int main() {
int i,k,x,y,z;
read(n); read(m);
for (i=1;i<n;i++) {
read(x); read(y);
addedge(x,y);
}
dfs1(1,0); dfs2(1,1,1);
for (i=1;i<=n;i++) read(v[i]);
read(root);
build(1,1,n);
for (i=1;i<=m;i++) {
read(k); read(x);
if (k==2) read(y),read(z);
if (k==1) root=x;
else if (k==2) modify(x,y,z);
else if (k==3) printf("%d\n",query(x));
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
const int M=110;
const int u[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,ans,a[M][M],id[M][M],cnt;
int g[N],to[N],nxt[N],f[N],tot=1;
int gap[N],h[N],d[N],s,t;
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
void addedge(int x,int y,int z) {
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot; f[tot]=z;
to[++tot]=x; nxt[tot]=g[y]; g[y]=tot; f[tot]=0;
}
int iSap(int x,int flow){
if (x==t) return flow;
int k,nowflow=0,rec;
for (k=h[x];k;k=nxt[k]) if (d[x]==d[to[k]]+1&&f[k]) {
rec=iSap(to[k],min(flow-nowflow,f[k]));
f[k]-=rec; f[k^1]+=rec; h[x]=k;
if ((nowflow+=rec)==flow) return flow;
}
h[x]=g[x];
if (!(--gap[d[x]])) d[s]=n;
gap[++d[x]]++;
return nowflow;
}
int main() {
int i,j,k,x,y;
read(n); read(m);
for (i=1;i<=n;i++) for (j=1;j<=m;j++) read(a[i][j]),id[i][j]=++cnt;
s=++cnt; t=++cnt;
for (i=1;i<=n;i++) for (j=1;j<=m;j++) {
if (a[i][j]==1) {
addedge(s,id[i][j],infi);
for (k=0;k<4;k++) {
x=i+u[k][0]; y=j+u[k][1];
if (x<1||x>n||y<1||y>m) continue;
if (a[x][y]==1) continue;
addedge(id[i][j],id[x][y],1);
}
} else if (a[i][j]==2) addedge(id[i][j],t,infi);
else if (a[i][j]==0) {
for (k=0;k<4;k++) {
x=i+u[k][0]; y=j+u[k][1];
if (x<1||x>n||y<1||y>m) continue;
if (a[x][y]==1) continue;
addedge(id[i][j],id[x][y],1);
}
}
}
for (i=1;i<=t;i++) h[i]=g[i];
gap[0]=n=t;
while (d[s]<n) ans+=iSap(s,infi);
printf("%d\n",ans);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
int n,m,ma[N<<3],tot;
int a[N],b[N],c[N],d[N];
void Max(int &x,int y) {if (x<y) x=y;}
void read(int &a) {
char ch; bool f=0; while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1,a=0; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
void build(int i,int l,int r) {
if (l==r) {
ma[i]=b[l];
return;
} int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
ma[i]=max(ma[i<<1],ma[i<<1|1]);
}
int ask(int i,int l,int r,int x,int y) {
if (x>y) return 0;
if (x<=l&&y>=r) return ma[i];
int mid=(l+r)>>1,ans=0;
if (x<=mid) Max(ans,ask(i<<1,l,mid,x,y));
if (y>mid) Max(ans,ask(i<<1|1,mid+1,r,x,y));
return ans;
}
int check(int l,int r,int x) {
int mid=0;
while (l<r) {
mid=(l+r)>>1;
if (x<=a[mid]) r=mid;
else l=mid+1;
} return r;
}
int main() {
int i,x,y,tx,ty,tmp;
for (read(n),i=1;i<=n;i++) read(a[i]),read(b[i]);
build(1,1,n); a[n+1]=infi; a[0]=-infi;
for (read(m),i=1;i<=m;i++) {
read(x); read(y);
tx=check(0,n+1,x);
ty=check(0,n+1,y);
if (a[tx]!=x&&a[ty]!=y) puts("maybe");
else if (x==y) puts("true");
else if (a[tx]!=x&&a[ty]==y) {
tmp=ask(1,1,n,tx,ty-1);
if (tmp>=b[ty]) puts("false");
else puts("maybe");
} else if (a[ty]!=y&&a[tx]==x) {
tmp=ask(1,1,n,tx+1,ty-1);
if (tmp>=b[tx]) puts("false");
else puts("maybe");
} else if (b[tx]<b[ty]) puts("false");
else {
tmp=ask(1,1,n,tx+1,ty-1);
if (tmp>=b[ty]) puts("false");
else if (y-x!=ty-tx) puts("maybe");
else puts("true");
}
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
char s[10];
int n,m,a[N];
ll h[N][2];
void add(int pos,ll x,int k) {while (pos<=n) h[pos][k]+=x,pos+=pos&-pos;}
ll sum(int pos,int k){ll t=0; while (pos>0) t+=h[pos][k],pos-=pos&-pos;return t;}
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
int main() {
int i,x,y;
read(n); read(m);
for (i=1;i<=n;i++) read(a[i]),add(i,a[i],0),add(i,(ll)a[i]*(n-i+1),1);
for (i=1;i<=m;i++) {
scanf("%s",&s); read(x);
if (s[0]=='Q') printf("%lld\n",sum(x,1)-(ll)sum(x,0)*(n-x));
else read(y),add(x,y-a[x],0),add(x,(ll)(y-a[x])*(n-x+1),1),a[x]=y;
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
int n,m; char s[10];
int ma[N<<2],evma[N<<2],la[N<<2][2],evla[N<<2][2];
bool f[N<<2];
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||(ch=='-')));
if (ch=='-') f=1,a=0; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
void build(int i,int l,int r) {
if (l==r) {
read(ma[i]);
evma[i]=ma[i];
return;
} int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
ma[i]=max(ma[i<<1],ma[i<<1|1]);
evma[i]=ma[i];
}
void add(int i,int x,int y) {
if (!f[i]) {
if (la[i][0]+y>evla[i][0]) evla[i][0]=la[i][0]+y;
la[i][0]+=x;
} else {
if (la[i][1]+y>evla[i][1]) evla[i][1]=la[i][1]+y;
la[i][1]+=x;
}
}
void clean(int i,int l,int r) {
if (!i) return;
if (la[i][0]||evla[i][0]||f[i]) {
if (la[i][0]||evla[i][0]) {
if (ma[i]+evla[i][0]>evma[i]) evma[i]=ma[i]+evla[i][0];
ma[i]+=la[i][0];
if (l!=r) {
add(i<<1,la[i][0],evla[i][0]);
add(i<<1|1,la[i][0],evla[i][0]);
}
la[i][0]=evla[i][0]=0;
}
if (f[i]) {
if (evla[i][1]>evma[i]) evma[i]=evla[i][1];
ma[i]=la[i][1];
if (l!=r) {
if (evla[i][1]>evla[i<<1][1]) evla[i<<1][1]=evla[i][1];
if (evla[i][1]>evla[i<<1|1][1]) evla[i<<1|1][1]=evla[i][1];
la[i<<1][1]=la[i<<1|1][1]=la[i][1];
f[i<<1]=f[i<<1|1]=1;
} f[i]=0;
la[i][1]=0; evla[i][1]=-infi;
}
}
}
void add(int i,int l,int r,int x,int y,int z) {
clean(i,l,r);
if (x<=l&&y>=r) {
la[i][0]=z;
if (la[i][0]>evla[i][0]) evla[i][0]=la[i][0];
clean(i,l,r);
return;
} int mid=(l+r)>>1;
if (x<=mid) add(i<<1,l,mid,x,y,z);
if (y>mid) add(i<<1|1,mid+1,r,x,y,z);
clean(i<<1,l,mid); clean(i<<1|1,mid+1,r);
ma[i]=max(ma[i<<1],ma[i<<1|1]);
if (ma[i]>evma[i]) evma[i]=ma[i];
}
void change(int i,int l,int r,int x,int y,int z) {
clean(i,l,r);
if (x<=l&&y>=r) {
la[i][1]=z;
evla[i][1]=z;
f[i]=1;
clean(i,l,r);
return;
} int mid=(l+r)>>1;
if (x<=mid) change(i<<1,l,mid,x,y,z);
if (y>mid) change(i<<1|1,mid+1,r,x,y,z);
clean(i<<1,l,mid); clean(i<<1|1,mid+1,r);
ma[i]=max(ma[i<<1],ma[i<<1|1]);
if (ma[i]>evma[i]) evma[i]=ma[i];
}
int query(int i,int l,int r,int x,int y) {
clean(i,l,r);
if (x<=l&&y>=r) return ma[i];
int mid=(l+r)>>1,ans=-infi;
if (x<=mid) ans=max(ans,query(i<<1,l,mid,x,y));
if (y>mid) ans=max(ans,query(i<<1|1,mid+1,r,x,y));
return ans;
}
int ask(int i,int l,int r,int x,int y) {
clean(i,l,r);
if (x<=l&&y>=r) return evma[i];
int mid=(l+r)>>1,ans=-infi;
if (x<=mid) ans=max(ans,ask(i<<1,l,mid,x,y));
if (y>mid) ans=max(ans,ask(i<<1|1,mid+1,r,x,y));
return ans;
}
int main() {
int i,x,y,z;
read(n); build(1,1,n);
for (read(m),i=1;i<=m;i++) {
scanf("%s",&s); read(x); read(y);
if (s[0]=='P'||s[0]=='C') read(z);
if (s[0]=='Q') printf("%d\n",query(1,1,n,x,y));
else if (s[0]=='A') printf("%d\n",ask(1,1,n,x,y));
else if (s[0]=='P') add(1,1,n,x,y,z);
else if (s[0]=='C') change(1,1,n,x,y,z);
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000100;
int n,a,b,c;
ll g[N],s[N];
int team[N],head,tail;
void read(ll &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
ll calc(int x,int y) {return a*(s[x]-s[y])*(s[x]-s[y])+c+g[y];}
ll calc2(int x,int y) {return g[x]-g[y]+a*s[x]*s[x]-a*s[y]*s[y];}
bool check(int i,int j,int k) {return calc2(i,j)*2*a*(s[j]-s[k])<calc2(j,k)*2*a*(s[i]-s[j]);}
int main() {
int i;
scanf("%d%d%d%d",&n,&a,&b,&c);
for (i=1;i<=n;i++) read(s[i]),s[i]+=s[i-1];
team[head=tail=1]=0;
for (i=1;i<=n;i++) {
while (head<tail&&calc(i,team[head])<calc(i,team[head+1])) head++;
g[i]=calc(i,team[head]);
while (head<tail&&check(i,team[tail],team[tail-1])) tail--;
team[++tail]=i;
} cout<<g[n]+(ll)b*s[n]<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
D x,y,ma,mi,ans=100000000.0;
int n;
void Max(D &x,D y) {if (x<y) x=y;}
void Min(D &x,D y) {if (x>y) x=y;}
D solve(D x,D y,int n) {
if (n==1) return max(x/y,y/x);
int i; D ans=100000000.0,tx,ty;
for (i=1;i<n;i++) {
tx=x*(i+0.0)/(n+0.0);
Min(ans,max(solve(tx,y,i),solve(x-tx,y,n-i)));
}
for (i=1;i<n;i++) {
ty=y*(i+0.0)/(n+0.0);
Min(ans,max(solve(x,ty,i),solve(x,y-ty,n-i)));
} return ans;
}
int main() {
scanf("%lf%lf%d",&x,&y,&n);
printf("%.6lf\n",solve(x,y,n));
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=150010;
priority_queue<int>q;
struct node{int x,y;}a[N];
int n,t,ans;
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1,a=0; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
bool cmp(const node &a,const node &b) {return a.y<b.y||a.y==b.y&&a.x<b.x;}
int main() {
int i;
for (read(n),i=1;i<=n;i++)
read(a[i].x),read(a[i].y);
sort(a+1,a+1+n,cmp);
for (i=1;i<=n;i++) {
if (a[i].x+t<=a[i].y) t+=a[i].x,q.push(a[i].x),ans++;
else if (a[i].x<=q.top()) {
if (t-q.top()+a[i].x<=a[i].y)
t=t-q.top()+a[i].x,q.pop(),q.push(a[i].x);
}
} cout<<ans<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000100;
int n,i,j,p[N],c[N];
int team[N],head,tail;
ll s[N],g[N],f[N],d[N];
ll calc(int j,int i) {return f[j]+g[i]-g[j]-s[j]*(d[i]-d[j]);}
ll calc2(int i,int j) {return s[i]*d[i]-g[i]+f[i]-s[j]*d[j]+g[j]-f[j];}
bool check(int i,int j,int k) {return calc2(i,j)*(s[j]-s[k])<calc2(j,k)*(s[i]-s[j]);}
int main() {
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%lld%d%d",&d[i],&p[i],&c[i]);
for (i=1;i<=n;i++) s[i]=s[i-1]+p[i],g[i]=g[i-1]+s[i-1]*(d[i]-d[i-1]);
team[head=tail=1]=0;
for (i=1;i<=n;i++) {
while (head<tail&&calc(team[head],i)>calc(team[head+1],i)) head++;
f[i]=calc(team[head],i)+c[i];
while (head<tail&&check(i,team[tail],team[tail-1])) tail--;
team[++tail]=i;
} cout<<f[n]<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10010;
struct node{int t,x,y;}a[N];
int i,j,n,m,f[N],ans;
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1,a=0; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
int Abs(int x) {return x>0?x:-x;}
void Max(int &x,int y) {if (x<y) x=y;}
int main() {
read(n); read(m);
for (i=1;i<=m;i++) read(a[i].t),read(a[i].x),read(a[i].y);
for (i=1;i<=m;i++) {
f[i]=1;
for (j=1;j<i;j++) {
if (a[i].t-a[j].t>=Abs(a[i].x-a[j].x)+Abs(a[i].y-a[j].y))
Max(f[i],f[j]+1);
} Max(ans,f[i]);
} cout<<ans<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,q,g[305][305];
int h[105][305][305];
void add(int k,int x,int pos,int z) {while (pos<=m) h[k][x][pos]+=z,pos+=(pos&(-pos));}
void insert(int k,int x,int y,int z) {while (x<=n) add(k,x,y,z),x+=(x&(-x));}
int ask(int k,int x,int pos) {int t=0; while (pos>0) t+=h[k][x][pos],pos-=(pos&(-pos));return t;}
int get(int k,int x,int y) {int t=0; while (x>0) t+=ask(k,x,y),x-=(x&(-x));return t;}
int main() {
int i,j,ans; int c,k,x1,x2,y1,y2;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) for (j=1;j<=m;j++) {
scanf("%d",&g[i][j]);
insert(g[i][j],i,j,1);
} scanf("%d",&q);
for (i=1;i<=q;i++) {
scanf("%d",&k);
if (k==1) {
scanf("%d%d%d",&x1,&y1,&c);
insert(g[x1][y1],x1,y1,-1);
g[x1][y1]=c;
insert(g[x1][y1],x1,y1,1);
} else {
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
ans=get(c,x2,y2)+get(c,x1-1,y1-1);
ans=ans-get(c,x1-1,y2)-get(c,x2,y1-1);
printf("%d\n",ans);
}
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=3010;
const int M=200010;
vector<int>v[N];
int n,m,d[N],w[N],ed[N];
int g[N],c[M],to[M],nxt[M],tot;
bool b[N];
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1,a=0; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
void addedge(int x,int y,int z) {
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot; c[tot]=z;
}
void Max(int &x,int y) {if (x<y) x=y;}
void dijkstra() {
int i,j,sz,x,k,ma;
for (i=1;i<=n;i++) d[i]=infi; d[1]=0;
for (i=1;i<=n;i++) {
ma=infi;
for (j=1;j<=n;j++) if (!b[j]&&!w[j]&&d[j]<ma) ma=d[j],x=j;
sz=v[x].size(); b[x]=1;
for (j=0;j<sz;j++) {
w[v[x][j]]--;
if (!w[v[x][j]]) Max(d[v[x][j]],d[x]);
}
for (k=g[x];k;k=nxt[k]) if (d[x]+c[k]<d[to[k]])
d[to[k]]=d[x]+c[k];
}
}
int main() {
int i,j,x,y,z;
read(n); read(m);
for (i=1;i<=m;i++) {
read(x); read(y); read(z);
addedge(x,y,z);
}
for (i=1;i<=n;i++) {
read(w[i]);
for (j=1;j<=w[i];j++) {
read(x);
v[x].push_back(i);
}
} dijkstra();
cout<<d[n]<<endl;
return 0;
}
#include <cstdio>
using namespace std;
typedef long long ll;
int n;
ll ans;
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) ans+=n/i;
printf("%lld\n",ans);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10001000;
int n,prime[N],phi[N],tot;
ll f[N],ans;
bool b[N];
void calc(int x){
b[1]=1;
int num,i;
for (i=2;i<=n;i++) phi[i]=i;
for (i=2;i<=x;i++){
if (b[i]) continue;
prime[++tot]=i;num=i;
while (num<=x) b[num]=1,(phi[num]/=i)*=(i-1),num+=i;
}
}
int main() {
int i;
scanf("%d",&n);
calc(n);
for (i=2;i<=n;i++) f[i]=(f[i-1]+phi[i]);
for (i=1;i<=n;i++) f[i]=f[i]<<1|1;
for (i=1;prime[i]<=n&&i<=tot;i++) ans+=f[n/prime[i]];
cout<<ans<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000100;
int n,a[N];
ll f[N],sum,need,tmp,ans;
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1,a=0; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
int Abs(int x) {return x>0?x:-x;}
int main() {
int i;
for (read(n),i=1;i<=n;i++) read(a[i]),sum+=a[i];
need=sum/n;
for (i=2;i<=n;i++) f[i]=need+f[i-1]-a[i];
sort(f+1,f+1+n);
tmp=f[n/2];
for (i=1;i<=n;i++) ans+=Abs(f[i]-tmp);
cout<<ans<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1010;
struct node{int x,y;}a[N];
int n,k,fa[N];
D d[N][N],l,r,mid;
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1,a=0; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
int sqr(int x) {return x*x;}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
bool check(D x) {
int i,j,fx,fy,num=n;
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<n;i++) for (j=i+1;j<=n;j++)
if (d[i][j]<=x) {
fx=find(i); fy=find(j);
if (fx==fy) continue;
fa[fx]=fy;
num--;
}
return num<k;
}
int main() {
int i,j;
read(n); read(k);
for (i=1;i<=n;i++) read(a[i].x),read(a[i].y);
for (i=1;i<n;i++) for (j=i+1;j<=n;j++)
d[i][j]=d[j][i]=sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y));
l=0.0; r=100000.0;
while (r-l>eps) {
mid=(l+r)/2.0;
if (check(mid)) r=mid;
else l=mid;
} printf("%.2lf",l);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=50010;
int n,phi[N],p[N],tot;
ll ans;
bool f[N];
void init() {
int i,j,t; f[1]=f[0]=1;
for (i=1;i<=n;i++) phi[i]=i;
for (i=2;i<=n;i++) if (!f[i]) {
p[++tot]=i;
for (j=i;j<=n;j+=i) {
f[j]=1;
phi[j]=phi[j]/i*(i-1);
}
}
}
int main() {
scanf("%d",&n);
init();
for (int i=2;i<n;i++) ans+=phi[i];
cout<<(ans<<1)+3<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=51061;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
struct LCT *null;
struct LCT {
LCT *fa,*son[2];
int sz,id;
int sum,v,lazy[2];
bool rev;
void newnode(int _id=0) {
fa=son[0]=son[1]=null; id=_id;
v=lazy[0]=sz=sum=1; lazy[1]=rev=0;
}
bool isroot() {return (fa==null)||(fa->son[0]!=this&&fa->son[1]!=this);}
void updata() {
LCT *x=this;
x->sum=(son[0]->sum+son[1]->sum+v)%mod;
x->sz=son[0]->sz+son[1]->sz+1;
}
void add(int x,int y) {
LCT *t=this;
if (t==null) return;
t->v=((ll)t->v*x)%mod;
t->v=(t->v+y)%mod;
t->sum=((ll)t->sum*x)%mod;
t->sum=(t->sum+(ll)y*t->sz)%mod;
t->lazy[0]=((ll)t->lazy[0]*x)%mod;
t->lazy[1]=((ll)t->lazy[1]*x)%mod;
t->lazy[1]=(t->lazy[1]+y)%mod;
}
void reverse() {
swap(son[0],son[1]);
rev^=1;
}
void clean() {
LCT *x=this;
if (x==null) return;
if (x->lazy[0]!=1||x->lazy[1]!=0) {
x->son[0]->add(x->lazy[0],x->lazy[1]);
x->son[1]->add(x->lazy[0],x->lazy[1]);
x->lazy[0]=1; x->lazy[1]=0;
}
if (x->rev) {
x->son[0]->reverse();
x->son[1]->reverse();
x->rev=0;
}
}
void rotate() {
LCT *x=this,*y=x->fa;
int w=(y->son[0]==x);
if (!y->isroot()) {
LCT *z=y->fa;
if (y==z->son[0]) z->son[0]=x;
if (y==z->son[1]) z->son[1]=x;
} x->fa=y->fa; y->fa=x;
if (x->son[w]!=null) x->son[w]->fa=y;
y->son[w^1]=x->son[w];
x->son[w]=y; y->updata();
}
void clear() {
if (this==null) return;
if (!isroot()) fa->clear();
this->clean();
}
void splay() {
LCT *x=this,*y,*z; x->clear();
while (!x->isroot()) {
y=x->fa; z=y->fa;
if (!y->isroot())
if ((z->son[0]==y)^(y->son[1]==x)) y->rotate();
else x->rotate();
x->rotate();
} x->updata();
}
void access() {
LCT *x=this,*y=null;
for (;x!=null;y=x,x=x->fa) {
x->splay();
x->son[1]=y;
x->updata();
}
}
void makeroot() {
LCT *x=this;
x->access();
x->splay();
x->reverse();
}
};
LCT pool[N],*v[N],*cur;
int n,m;
char s[10];
void init() {
cur=pool; null=cur++;
null->newnode();
null->sum=null->sz=null->v=0;
}
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void link(int x,int y) {
v[y]->makeroot();
v[y]->fa=v[x];
v[y]->access();
}
void cut(int x,int y) {
v[x]->makeroot();
v[y]->access();
v[y]->splay();
v[y]->son[0]->fa=null;
v[y]->son[0]=null;
v[y]->updata();
}
void add(int x,int y,int z,int w) {
v[x]->makeroot();
v[y]->access();
v[y]->splay();
v[y]->add(z,w);
v[y]->clean();
}
int query(int x,int y) {
v[x]->makeroot();
v[y]->access();
v[y]->splay();
return v[y]->sum;
}
int main() {
int i,x,y,z,w,t;
read(n); read(m); init();
for (i=1;i<=n;i++) {
v[i]=cur++;
v[i]->newnode(i);
}
for (i=1;i<n;i++) {
read(x); read(y);
link(x,y);
}
for (i=1;i<=m;i++) {
scanf("%s",&s); read(x); read(y);
if (s[0]=='+') read(z),add(x,y,1,z);
else if (s[0]=='*') read(z),add(x,y,z,0);
else if (s[0]=='-') {
cut(x,y);
read(x);
read(y);
link(x,y);
} else if (s[0]=='/') printf("%d\n",query(x,y));
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=200010;
const int M=500010;
char s[10];
int n,m,w[N],num[N],fa[N];
int g[N],to[N],nxt[N],tot;
int top[N],pos[N],dfn[N],df;
int c[N],dep[N],lc[M],rc[M];
int lazy[M],cut[M];
int cur,ans;
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1,a=0; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
void addedge(int x,int y) {
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void dfs(int x,int fat) {
fa[x]=fat;
for (int k=g[x];k;k=nxt[k]) if (to[k]!=fat) {
dfs(to[k],x);
if (num[to[k]]>num[w[x]]) w[x]=to[k];
num[x]+=num[to[k]];
} num[x]++;
}
void dfs2(int x,int depth,int tail) {
dep[x]=depth; top[x]=tail;
dfn[x]=++df; pos[df]=x;
if (w[x]) dfs2(w[x],depth+1,tail);
for (int k=g[x];k;k=nxt[k]) {
if (to[k]==fa[x]||to[k]==w[x]) continue;
dfs2(to[k],depth+1,to[k]);
}
}
void build(int i,int l,int r) {
lazy[i]=-1;
if (l==r) {
lc[i]=rc[i]=c[pos[l]];
cut[i]=1;
return;
} int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
cut[i]=cut[i<<1]+cut[i<<1|1];
if (rc[i<<1]==lc[i<<1|1]) cut[i]--;
lc[i]=lc[i<<1]; rc[i]=rc[i<<1|1];
}
void clean(int i,int l,int r) {
if (!i) return;
if (lazy[i]!=-1) {
lc[i]=rc[i]=lazy[i];
cut[i]=1;
if (l!=r) lazy[i<<1]=lazy[i<<1|1]=lazy[i];
lazy[i]=-1;
}
}
void change(int i,int l,int r,int x,int y,int z) {
clean(i,l,r);
if (x<=l&&y>=r) {
lazy[i]=z;
clean(i,l,r);
return;
} int mid=(l+r)>>1;
if (x<=mid) change(i<<1,l,mid,x,y,z);
if (y>mid) change(i<<1|1,mid+1,r,x,y,z);
clean(i<<1,l,mid); clean(i<<1|1,mid+1,r);
cut[i]=cut[i<<1]+cut[i<<1|1];
if (rc[i<<1]==lc[i<<1|1]) cut[i]--;
lc[i]=lc[i<<1]; rc[i]=rc[i<<1|1];
}
void modify(int x,int y,int z) {
while (top[x]!=top[y]) {
if (dep[top[x]]>dep[top[y]]) change(1,1,n,dfn[top[x]],dfn[x],z),x=fa[top[x]];
else change(1,1,n,dfn[top[y]],dfn[y],z),y=fa[top[y]];
} dep[x]<dep[y]?change(1,1,n,dfn[x],dfn[y],z):change(1,1,n,dfn[y],dfn[x],z);
}
void ask(int i,int l,int r,int x,int y) {
clean(i,l,r);
if (x<=l&&y>=r) {
ans+=cut[i];
if (lc[i]==cur) ans--;
cur=rc[i];
return;
} int mid=(l+r)>>1;
if (x<=mid) ask(i<<1,l,mid,x,y);
if (y>mid) ask(i<<1|1,mid+1,r,x,y);
}
int get(int x,int y) {
ans=0; cur=-1;
ask(1,1,n,x,y);
return ans;
}
int get_c(int i,int l,int r,int x) {
clean(i,l,r);
if (l==r) return lc[i];
int mid=(l+r)>>1;
return x<=mid?get_c(i<<1,l,mid,x):get_c(i<<1|1,mid+1,r,x);
}
int query(int x,int y) {
int ans=0,t1,t2;
while (top[x]!=top[y]) {
if (dep[top[x]]>dep[top[y]]) {
ans+=get(dfn[top[x]],dfn[x]);
t1=get_c(1,1,n,dfn[top[x]]);
t2=get_c(1,1,n,dfn[fa[top[x]]]);
if (t1==t2) ans--;
x=fa[top[x]];
} else {
ans+=get(dfn[top[y]],dfn[y]);
t1=get_c(1,1,n,dfn[top[y]]);
t2=get_c(1,1,n,dfn[fa[top[y]]]);
if (t1==t2) ans--;
y=fa[top[y]];
}
}
if (dep[x]<dep[y]) return ans+get(dfn[x],dfn[y]);
else return ans+get(dfn[y],dfn[x]);
}
int main() {
int i,x,y,z;
read(n); read(m);
for (i=1;i<=n;i++) read(c[i]);
for (i=1;i<n;i++) {
read(x); read(y);
addedge(x,y);
} dfs(1,0); dfs2(1,1,1);
build(1,1,n);
for (i=1;i<=m;i++) {
scanf("%s",&s); read(x); read(y);
if (s[0]=='C') {
read(z);
modify(x,y,z);
} else if (s[0]=='Q') printf("%d\n",query(x,y));
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=2000100;
int n,m,ans,belong[N];
int g[N],nxt[N],to[N],tot;
int v[N],c[N];
void addedge(int x,int y){
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
}
bool find(int x,int t){
for (int k=g[x];k;k=nxt[k]){
if (v[to[k]]!=t) {
v[to[k]]=t;
if (!belong[to[k]]||find(belong[to[k]],t)) {
belong[to[k]]=x;
return 1;
}
}
}
return 0;
}
void read(int &a) {
char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
if (ch=='-') f=1,a=0; else a=ch-'0';
while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
if (f) a=-a;
}
int main() {
int i,x,y;
for (read(n),i=1;i<=n;i++) {
read(x); read(y);
addedge(x,i);
addedge(y,i);
c[x]++; c[y]++;
}
for (i=1;;i++) {
if (!c[i]) return printf("%d\n",i-1),0;
if (!find(i,i)) return printf("%d\n",i-1),0;
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int mod=12345678;
int n,x,y,K,ans;
int f[320][180][25][25];
int main() {
int i,j,k,l;
scanf("%d%d%d",&x,&y,&K); n=x+y;
f[0][0][0][0]=1;
for (i=0;i<n;i++) {
for (j=0;j<=min(i,x);j++) for (k=0;k<=K;k++) for (l=0;l<=K;l++) {
(f[i+1][j+1][k+1][max(l-1,0)]+=f[i][j][k][l])%=mod;
(f[i+1][j][max(k-1,0)][l+1]+=f[i][j][k][l])%=mod;
}
}
for (i=0;i<=K;i++) for (j=0;j<=K;j++) ans=(ans+f[n][x][i][j])%mod;
printf("%d\n",ans);
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=400010;
const int infi=100000000;
int n,m,S,T,tot=1;
int g[510],nxt[N],to[N],f[N],c[N];
int mincost,tmpflow,ans;
int team[N],pre[510],d[510],head,tail;
bool in[510];
void addedge(int x,int y,int z,int w){
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot; f[tot]=z; c[tot]=w;
to[++tot]=x; nxt[tot]=g[y]; g[y]=tot; f[tot]=0; c[tot]=-w;
}
bool spfa(){
int i,k,x;
for (i=S;i<=T;i++) d[i]=infi,in[i]=0;
team[head=tail=0]=S;
d[S]=0; in[S]=1;
while (head<=tail){
in[x=team[head++]]=0;
for (k=g[x];k;k=nxt[k])
if (f[k]&&d[x]+c[k]<d[to[k]]){
d[to[k]]=d[x]+c[k];
pre[to[k]]=k;
if (!in[to[k]]) {
in[to[k]]=1;
team[++tail]=to[k];
}
}
}
return d[T]!=infi;
}
void augment(){
int i; tmpflow=infi; ans++;
for (i=pre[T];i;i=pre[to[i^1]]) tmpflow=min(tmpflow,f[i]);
for (i=pre[T];i;i=pre[to[i^1]]) f[i]-=tmpflow,f[i^1]+=tmpflow,mincost+=c[i]*tmpflow;
}
int main(){
int i,j,x,y,z;
scanf("%d%d",&n,&m); S=1; T=n+n;
for (i=1;i<=m;i++) {
scanf("%d%d%d",&x,&y,&z);
addedge(x+n,y,1,z);
}
for (i=2;i<n;i++) addedge(i,i+n,1,0);
addedge(1,n+S,200,0); addedge(n,T,200,0);
while (spfa()) augment();
printf("%d %d\n",ans,mincost);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=250010;
char s[10];
int n,m,fa[N];
int num[N],w[N],top[N],dfn[N],df;
int g[N],to[N<<1],nxt[N<<1],tot;
int f[N<<2];
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void addedge(int x,int y) {
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void dfs(int x,int fat) {
fa[x]=fat;
for (int k=g[x];k;k=nxt[k]) if (to[k]!=fat) {
dfs(to[k],x);
if (num[to[k]]>num[w[x]]) w[x]=to[k];
num[x]+=num[to[k]];
} num[x]++;
}
void dfs2(int x,int tail) {
dfn[x]=++df; top[x]=tail;
if (w[x]) dfs2(w[x],tail);
for (int k=g[x];k;k=nxt[k]) {
if (to[k]==fa[x]||to[k]==w[x]) continue;
dfs2(to[k],to[k]);
}
}
void build(int i,int l,int r) {
if (l==r) {
f[i]=1;
return;
} int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
f[i]=f[i<<1]+f[i<<1|1];
}
void change(int i,int l,int r,int x) {
if (l==r) {
f[i]=0;
return;
} int mid=(l+r)>>1;
if (x<=mid) change(i<<1,l,mid,x);
else change(i<<1|1,mid+1,r,x);
f[i]=f[i<<1]+f[i<<1|1];
}
int ask(int i,int l,int r,int x,int y) {
if (x<=l&&y>=r) return f[i];
int mid=(l+r)>>1,ans=0;
if (x<=mid) ans+=ask(i<<1,l,mid,x,y);
if (y>mid) ans+=ask(i<<1|1,mid+1,r,x,y);
return ans;
}
int query(int x) {
int ans=0;
while (top[x]!=1) ans+=ask(1,1,n,dfn[top[x]],dfn[x]),x=fa[top[x]];
ans+=ask(1,1,n,1,dfn[x])-1;
return ans;
}
int main() {
int i,x,y;
for (read(n),i=1;i<n;i++) {
read(x); read(y);
addedge(x,y);
}
dfs(1,1); dfs2(1,1);
build(1,1,n);
for (read(m),i=1;i<n+m;i++) {
scanf("%s",&s);
if (s[0]=='A') {
read(x); read(y);
if (fa[y]!=x) swap(x,y);
change(1,1,n,dfn[y]);
} else if (s[0]=='W') {
read(x);
printf("%d\n",query(x));
}
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
struct node{
int id,pri,st,tm;
friend bool operator < (node a,node b) {return a.pri<b.pri||(a.pri==b.pri&&a.st>b.st);}
}t,w;
priority_queue<node> q,q1;
int now;
void print() {
node t=q.top(),w; q.pop();
printf("%d %d\n",t.id,now+t.tm);
now+=t.tm;
}
int main() {
while (~scanf("%d%d%d%d",&t.id,&t.st,&t.tm,&t.pri)) {
if (q.empty()) {
q.push(t);
now=max(t.st,now);
} else {
if (t.st>=now) while (!q.empty()) {
w=q.top();
if (now+w.tm<=t.st) print();
else {
w.tm-=t.st-now;
q.pop();
q.push(w);
break;
}
} q.push(t);
now=max(t.st,now);
}
} while (!q.empty()) print();
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000100;
vector<int >v[70];
vector<int >g[N];
int n,m,tot,b[N];
int f[N],num,ans=infi,last;
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
int check(int l,int r,int x) {
int mid;
while (l<r) {
mid=(l+r)>>1;
if (x<=b[mid]) r=mid;
else l=mid+1;
} return r;
}
int main() {
int i,j,sz,x,y;
read(n); read(m);
for (i=1;i<=m;i++) {
read(x);
for (j=1;j<=x;j++) {
read(y);
b[++tot]=y;
v[i].push_back(y);
}
}
sort(b+1,b+1+n);
for (i=1;i<=m;i++) {
sz=v[i].size();
for (j=0;j<sz;j++) {
x=check(1,n,v[i][j]);
g[x].push_back(i);
}
} last=1; b[0]=-1;
for (i=1;i<=n;i++) {
if (b[i]==b[i-1]) continue;
sz=g[i].size();
for (j=0;j<sz;j++) {
if (f[g[i][j]]==0) num++;
f[g[i][j]]++;
} while (num==m&&last<i) {
ans=min(ans,b[i]-b[last]);
sz=g[last].size();
for (j=0;j<sz;j++) {
f[g[last][j]]--;
if (f[g[last][j]]==0) num--;
} last++;
}
} cout<<ans<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=2097152;
const int M=30;
int S,f[N],d[N],t[M],h[M],s[M];
int n,H,ans=-1;
bool b[N];
void Max(int &x,int y) {if (x<y) x=y;}
int main() {
int i;
scanf("%d%d",&n,&H);
for (i=0;i<n;i++) scanf("%d%d%d",&h[i],&t[i],&s[i]);
f[0]=infi;
for (S=0;S<(1<<n);S++) {
for (i=0;i<n;i++) if (!(S&(1<<i))) {
d[S^(1<<i)]=d[S]+h[i];
if (f[S]>=t[i]) {
Max(f[S^(1<<i)],min(f[S]-t[i],s[i]));
if (d[S^(1<<i)]>=H) Max(ans,f[S^(1<<i)]);
}
}
} if (ans!=-1) cout<<ans<<endl;
else puts("Mark is too tall");
return 0;
}
2022年8月23日 01:15
This board is linked with a large number of public, private, and colleges, and all of them operate under its supervision. For the students in this state, this board offers a variety of courses and administers exams, in which a large number of students participate. Numerous kids are now enrolled in class 11, and the Odisha Board 11th class Important Question Paper 2023 will be available soon. In the month of May, CHSE 11th Question Paper 2023 the CHSE 11th Question Paper 2023 was released. Therefore, all of the students who took the class 11th examinations this year are eagerly awaiting the release of the CHSE 11th Important Question Paper 2023.