```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define mp make_pair
#define F first
#define S second
#define sqr(x) ((x)*(x))
typedef long long ll;
const double eps=1e-8;
inline int sgn(double x) {return x<-eps ? -1 :x>eps;}
struct Poi ;
typedef Poi Vec;
struct Poi
{
double x,y;
Poi () {}
Poi (double x,double y): x(x),y(y) {}
void in() {scanf("%lf %lf",&x,&y);}
double operator * (Vec b) {return x*b.y-b.x*y;}//cj
Vec operator * (double t) {return Vec(x*t,y*t);}
Vec operator - (Vec b) {return Vec(x-b.x,y-b.y);}
Vec operator + (Vec b) {return Vec(x+b.x,y+b.y);}
double dot(Vec b) {return x*b.x+y*b.y;}//dj
};
struct line
{
Poi a,b;
line () {}
line (Poi a,Poi b): a(a),b(b) {}
void ml(Poi x,Poi y) {a=x; b=y;}
void in() {a.in(),b.in();}
bool P_on_L (Poi p) {return (a-p)*(b-p)==0;}
};
struct Seg
{
Poi a,b;
Seg () {}
Seg (Poi a,Poi b): a(a),b(b) {}
void ms(Poi x,Poi y) {a=x; b=y;}
void in() {a.in(),b.in();}
bool P_on_S (Poi p) {return sgn((a-p)*(b-p))==0 && sgn((a-p).dot(b-p))<=0;}
};
Poi p[210];
Seg s[210];
int n;
bool L_inter(line a,line b,Poi &to)
{
Poi p=a.a,q=b.a;
Vec v=a.b-a.a,w=b.b-b.a,u=p-q;
if(sgn(w*v)==0) return false;
double t=(u*w)/(v*w);//remember
to=p+v*t;
return true;
}
bool S_inter(Seg a,Seg b,Poi &to)
{
line _a(a.a,a.b),_b(b.a,b.b);
if(L_inter(_a,_b,to) && a.P_on_S(to) && b.P_on_S(to)) return true;
return false;
}
bool LS_inter(line a,Seg b,Poi &to)
{
line _a(a.a,a.b),_b(b.a,b.b);
if(L_inter(_a,_b,to) && b.P_on_S(to)) return true;
return false;
}
bool work(int x,int y)
{
line tmp(p[x],p[y]); Poi t;
for(int i=1;i<=n;i++)
if(!LS_inter(tmp,s[i],t)) {printf("%d ",i); return false;}
return true;
}
int main()
{
int T,i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n); bool flag=0;
for(i=1;i<=n*2;i++) p[i].in();
for(i=2;i<=n*2;i+=2) s[i/2].ms(p[i-1],p[i]);
for(i=1;i<=n*2;i++)
{
for(j=1;j<=n*2;j++)
if(work(i,j)) {puts("Yes!");flag=1; break;}
if(flag) break;
}
if(flag) continue;
puts("No!");
}
return 0;
}
```
by functionendless @ 2017-07-11 20:40:33
```cpp
#include<cstdio>
#include<cstring>
#define N 100010
using namespace std;
int n;
struct Poi {double x,y; Poi(){} Poi(double x,double y):x(x),y(y) {}}
struct Seg {Poi a,b; Seg(){} Seg(Poi x,Poi y):x(x),y(y) {}}seg[N];
bool used[N];
inline void clear() {memset(used,0,sizeof(used));}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
clear();
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf %lf %lf %lf",&seg[i].a.x,&seg[i].a.y,&seg[i].b.x,&seg[i].b.y);
for(j=1;j<i;j++)
if(!used[j])
if(inter(seg[i],seg[j])) used[j]=1;
}
printf("Top sticks: ") for(i=1;i<=n;i++) if(!used[i]) printf(", %d",i); puts(".");
}
return 0;
}
```
by functionendless @ 2017-07-13 20:34:05
```cpp
#include<cstdio>
#include<cstring>
#define N 1510
using namespace std;
const double eps=1e-8;
int n;
int head[N],nxt[N<<1],to[N<<1],lst=0;
int sz[N];
struct P {int x,y,pos;} p[N];
inline int sgn(double x) {return x<-eps ? -1 : x>eps;}
inline void adde(int x,int y) {nxt[++lst]=head[x]; to[lst]=y; head[x]=lst;}
inline double cj()
void build_tre(int u,int f)
{
sz[u]=1;
for(i=head[u];i;i=nxt[i]) if(to[i]!=f) {build_tre(to[i]); sz[u]+=sz[to[i]];}
}
void dfs(int u,int l,int r)
{
if (l>r) return;
P tmp=p[l];
int pos=l;
for (int i=l;i<=r;++i)
if (p[i].y<tmp.y || (p[i].y==tmp.y && p[i].x<tmp.x)) {tmp=p[i];pos=i;}
ans[tmp.num]=u;
swap(p[pos],p[l]);
if (l==r) return;
for (int i=l+1;i<=r;i++)
{
p[i].x-=p[l].x;
p[i].y-=p[l].y;
}
sort(p+l+1,p+r+1,cmp);
int now=l+1;
for (int i=h[root];i;i=next[i])
if (size[toit[i]]<size[root])
{
dfs(toit[i],now,now+sz[toit[i]]-1);
now+=sz[toit[i]];
}
}
int main()
{
int i,x,y;
scanf("%d",&n);
for(i=1;i<n;i++) {scanf("%d %d",&x,&y); adde(x,y),adde(y,x);}
for(i=1;i<=n;i++){scanf("%d %d",&p[i].x,&p[i].y); p[i].pos=i;}
build_tre(1,0);
dfs(1,1,n);
return 0;
}
```
by functionendless @ 2017-07-20 16:01:26
```cpp
#include<bits/stdc++.h>
#define lc (u<<1)
#define rc (lc+1)
#define left lc,l,r
#define right rc,l,r
#define mid ((s[u]+e[u])>>1)
#define pb push_back
#define N 100010
using namespace std;
int n,o[10];
struct P {int x,y;}px[N],py[N];
map<int,int> key,_key; int num[N<<2],lst,cnt;
int s[N<<2],e[N<<2]; vector <int> poi[N<<2];
bool cmp1(P a,P b) {return a.x==b.x ? a.y<b.y : a.x<b.x;}
bool cmp2(P a,P b) {return a.y==b.y ? a.x<b.x : a.y<b.y;}
void build_tre(int u,int l,int r)
{
s[u]=l,e[u]=r;
for(int i=l;i<=r;i++) poi[u].pb(px[i].y);
sort(poi[u].begin(),poi[u].end());
if(l==r) return;
build_tre(lc,l,mid); build_tre(rc,mid+1,r);
}
int query(int u,int l,int r,int v){
if(l<=s[u] && e[u]<=r)
{
printf("%d %d %d %d\n",poi[u][poi[u].size()-1],poi[u].size(),l,r);
if(poi[u].size()==0 || poi[u][0]>v) return 0;
if(poi[u][poi[u].size()-1]<=v) return poi[u].size();
return upper_bound(poi[u].begin(),poi[u].end(),v)-poi[u].begin();
}
int ans=0;
if(l<=mid) ans+=query(left,v);
if(r> mid) ans+=query(right,v);
return ans;
}
bool ok()
{
int sx1=o[1]+o[2]+o[3],sx2=sx1+o[4]+o[5]+o[6],sy1=o[1]+o[4]+o[7],sy2=sy1+o[2]+o[5]+o[8];
int x1=px[sx1].x,x2=px[sx2].x,y1=py[sy1].y,y2=py[sy2].y;
if(x1+1>=n || x1==px[sx1+1].x) return false;
if(x2+1>=n || x2==px[sx2+1].x) return false;
if(y1+1>=n || y1==py[sy1+1].y) return false;
if(y2+1>=n || y2==py[sy2+1].y) return false;
if(query(1,1,x1,y1)!=o[1]) return false;puts("?");
printf("%d %d %d %d %d\n",x1,x2,y1,y2,query(1,1,x1,y2));
if(query(1,1,x1,y2)!=o[1]+o[2]) return false;
if(query(1,x1+1,x2,y1)!=o[4]) return false;
if(query(1,x1+1,x2,y2)!=o[4]+o[5]) return false;
printf("%d.5 %d.5\n%d.5 %d.5",x1,x2,y1,y2);
}
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d %d",&px[i].x,&px[i].y),num[++lst]=px[i].x,num[++lst]=px[i].y;
for(i=1;i<=9;i++) scanf("%d",&o[i]); sort(o+1,o+10);
sort(num+1,num+lst+1);
for(i=1;i<=lst;i++) if(!key[num[i]]) key[num[i]]=++cnt,_key[cnt]=num[i];
for(i=1;i<=n;i++) px[i].x=key[px[i].x],px[i].y=key[px[i].y];
sort(px+1,px+n+1,cmp2); for(i=1;i<=n;i++) py[i]=px[i];
sort(px+1,px+n+1,cmp1);
build_tre(1,1,n);
do if(ok()) return 0; while(next_permutation(o+1,o+10));
puts("-1");
return 0;
}
```
/\*9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
1 1 1 1 1 1 1 1 1\*/
by functionendless @ 2017-07-24 16:02:14
```cpp
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define N 3010
using namespace std;
int n,a[N],f[N][N],m[N][N],s[N],e[N],ma[N],mi[N],lst=0;
inline void init()
{
int i,j;
for(i=0;i<=n;i++) for(j=0;j<=n;j++) f[i][j]=(i==j+1 ? 0 :-1);
int now=0,posma,posmi,cnt=0,pre=1;
for(j=1;j<=n;j++)
{
if(a[j]>now) {now=a[j]; posma=j;}
if(a[j]==pre) posmi=j;
if(j==now) {s[++lst]=pre; e[lst]=now; mi[lst]=posmi; ma[lst]=posma; pre=j+1;}
}
for(i=1;i<=n;i++)
{
int mi=100000,ma=0;
for(j=i;j<=n;j++)
{
mi=min(a[j],mi); ma=max(a[j],ma);
if(ma-mi==j-i)
{
if(f[i][j-1]==-1 || f[i][j-1]==0)
{
int now=0; cnt=0;
for(int k=i;k<=j;k++)
{
if(a[k]>now) now=a[k];
if(mi+k-i==now) cnt++;
}
f[i][j]=cnt;
}
else
{
if(a[j]==mi) f[i][j]=1;
else f[i][j]=f[i][j-1]+1;
}
m[i][j]=mi;
}
}
}
}
bool judge(int s,int e)
{
int mi1=100000,ma1=0;
for(int i=s;i<=e;i++) mi1=min(mi1,a[i]),ma1=max(ma1,a[i]);
if(e-s+1!=ma1-mi1+1) return false;
return true;
}
int main()
{
int i,j,k,T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);lst=0;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
init(); int ans=f[1][n];
for(i=1;i<=lst;i++)
{
j=ma[i]-1,k=mi[i]+1;
while(1)
{
for(j=j+1;j<=e[i];j++) if(judge(s[i],j)) break;
for(k=k-1;k>=s[i];k--) if(judge(k,e[i])) break;
if(j>=k) break;
//printf("%d %d %d %d %d?\n",f[3][4],e[i-1]+j-s[i]+1+1,m[j+1][k-1],j,k);
if(f[j+1][k-1]!=-1 && e[i-1]+j-s[i]+1+1==m[j+1][k-1]) {ans=max(ans,f[1][n]+1+f[j+1][k-1]); break;}
}
}
printf("%d\n",ans);
}
return 0;
}
```
/\*
5
6
6 5 3 4 1 2
6
6 3 5 4 1 2
5
2 1 4 5 3
5
1 5 4 3 2
5
4 5 1 2 3\*/
by functionendless @ 2017-07-27 21:15:12
```cpp
#include<bits/stdc++.h>
#define N 300010
#define INF 1000000000
#define lc (u<<1)
#define rc (lc+1)
#define left lc,l,r
#define right rc,l,r
#define mid ((s[u]+e[u])>>1)
using namespace std;
int n,K,a[N];
vector<int> f[N];
int head[N],nxt[N<<1],to[N<<1],lst=0;
int s[N<<2],e[N<<2],v[N<<2],w[N<<2],sum[N<<2],cnt=0; int key[N];
int anc[N][30],dep[N];
inline void adde(int x,int y) {nxt[++lst]=head[x]; to[lst]=y; head[x]=lst;}
inline int lca(int a,int b)
{
if(dep[a]<dep[b]) swap(a,b);
for(int i=26;i>=0;i--)
if(dep[anc[a][i]]>=dep[b])
a=anc[a][i];
if(a==b) return a;
for(int i=26;i>=0;i--)
if(anc[a][i]!=anc[b][i])
a=anc[a][i],b=anc[b][i];
return anc[a][0];
}
inline void Build(int u,int f)
{
for(int i=head[u];i;i=nxt[u])
if(to[i]!=f)
{
anc[to[i]][0]=u;
dep[to[i]]=dep[u]+1;
Build(to[i],u);
}
}
inline void init_lca()
{
dep[1]=1; Build(1,0);
for(int j=1;j<26;j++)
for(int i=1;i<=n;i++)
anc[i][j]=anc[anc[i][j-1]][j-1];
}
void build_tre(int u,int l,int r)
{
s[u]=l; e[u]=r; v[u]=w[u]=sum[u]=INF;
if(l==r) {key[l]=u; return;}
}
inline void pd(int u)
{
if(v[u]!=INF)
{
v[lc]=v[rc]=v[u];
sum[lc]=v[lc]+f[][]
}
}
int update(int u,int l,int r,int w)
{
if(l<=s[u] && e[u]<=r) {v[u]=w; return ;}
pd(u);
if(l<=mid) update(left,w);
if(r> mid) update(right,w);
}
int query(int u,int l,int r)
{
if(l<=s[u] && e[u]<=r) return sum[u];
int ans=100000000; pd(u);
if(l<=mid) ans=min(ans,query(left));
if(r> mid) ans=min(ans,query(right));
return ans;
}
void insert(int val,int u)
{
v[u]=val;
}
int bsearch(int l,int r)
{
int ans;
while(l<=r)
{
int mi=(l+r)>>1;
if(v[key[mi]]) {l=mi-1; ans=mi;}
else r=mi+1;
}
return ans;
}
int main()
{
int T,i,j;
scanf("%d",&n,&K);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<n;i++) {scanf("%d %d",&x,&y); adde(x,y),adde(y,x};}
build_tre(1,1,n); init_lca();
for(i=1;i<=K;i++)
for(j=1;j<=n;j++)
{
int lc=lca(a[j-1],a[j]);
f[i][j]=query(1,i-1,j-1);
insert(dep[lc],key[j]);
int pos=bsearch(i-1,j-1);
update(u,pos,j-1,lc);
}
printf("%d",f[k][n]);
return 0;
}
```
by functionendless @ 2017-08-01 16:56:17
```cpp
#include<bits/stdc++.h>
#define N 100010
#define ll long long
using namespace std;
char s[N],t[N]; int ls,lt;
int pre[N],suf[N],nxt[N];
int cp[N],cs[N];
ll ans=0;
int main()
{
int T,i,j;
scanf("%d",&T);
while(T--)
{
scanf("%s%s",s,t); ls=strlen(s); lt=strlen(t); ans=0;
int now=0; nxt[0]=-1;
for(i=0;i<=lt;i++)
{
if(t[i]==t[now]) {now++; continue;}
if(t[i]!=t[now]) {nxt[i]=now; now=0; continue;}
}
now=0;
for(i=0;i<ls;i++)
{
int st=i; //printf("?%d?",st);
while(s[i]==t[now] && now<lt) i++,now++;
pre[st]=now;
while(now!=-1 && t[now]!=s[i]) now=nxt[now];
if(now==-1) {now=0; continue;}
i--; continue;
}
for(i=0;i<ls;i++)
{
for(j=lt-1;j>=0;j--)
if(s[i+lt-1-j]!=t[j]) break;suf[i]=lt-j-1;
}
for(int i=0;i<ls;i++) cp[pre[i]]++,cs[suf[i]]++;
for(int i=lt;i>=0;i--) cp[i]+=cp[i+1],cs[i]+=cs[i+1];
// for(int i=0;i<ls;i++) printf("%d ",pre[i]); puts("");
// for(int i=0;i<ls;i++) printf("%d ",suf[i]); puts("");
// for(int i=0;i<lt;i++) printf("%d ",cp[i]); puts("");
// for(int i=0;i<lt;i++) printf("%d ",cs[i]); puts("");
for(int i=1;i<lt;i++) ans+=(ll)cp[i]*cs[lt-i];
printf("%lld\n",ans);
}
return 0;
}
```
by functionendless @ 2017-08-11 15:18:21
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int a[26],cnt=0,f[26][3],ans=0;//0->no 1->lst=9 2->ok
void init_f()
{
f[0][0]=1;
for(int i=1;i<=24;i++)
{
f[i][2]=f[i-1][2]*10+f[i-1][1];
f[i][1]=f[i-1][0];
f[i][0]=f[i-1][0]*10-f[i-1][1];
}
}
int main()
{
int T;
init_f();
scanf("%d",&T);
while(T--)
{
scanf("%I64d",&n); cnt=0;
while(n) {a[++cnt]=n%10; n/=10;}
if(a[cnt]>=4) ans+=f[cnt-1][1];
for(int i=cnt;i>=1;i--)
{
}
printf("%d\n",ans);
}
return 0;
}
```
by functionendless @ 2017-09-02 15:53:34
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#define N 110
using namespace std;
int read()
{
char ch=getchar();int x=0,f=1;
while(!isdigit(ch) && ch!='-') ch=getchar(); if(ch=='-') f=-1,ch=getchar();
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
string Mon[]={"","January","February","March","April","May","June","July","August","September","October","November","December"};
int dat[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int n,dp[N*N*4][N] ,l,r,date,ans,Y[N];
string month,ty;
vector<int>have[12][35];
int find(string s) {for(int i=1;i<=12;i++) if(Mon[i]==s) return i;}
struct Q
{
int mo,da,ty,mm,dd;
friend bool operator < (Q x , Q y) {return x.da<y.da || (x.mo==y.mo && x.mo<y.mo);}
}xx[1010];
struct NODE {int year,mon,date;}ind,now;
void nxt(NODE &cur)
{
cur.date++;
if(cur.date==29 && cur.mon ==2)
{
if((cur.year % 4 == 0 && cur.year % 100 != 0) || (cur.year % 400 == 0)) return;
else {cur.date=1; cur.mon=3;}
}
if(cur.date>dat[cur.mon]) {cur.date=1; cur.mon++;}
if(cur.mon==13) {cur.mon=1; cur.year++;}
}
int main()
{
scanf("%d %d %d",&l,&r,&n);
for(int i = 1;i <= n;i ++)
{
cin>>month; date=read(); xx[i].mo=find(month); xx[i].da=date;
cin>> ty; xx[i].ty=(ty=="added");
cin>>month; date=read(); xx[i].mm=find(month); xx[i].dd=date;
}
ans=2e9;
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
ind.year = l; ind.mon = 1; ind.date = 1; int tot = 1;
while(ind.year != r + 1) {
for(int i = 0;i <= n;i ++) if(dp[tot - 1][i] >= 0){
int res = 0;
for(int j = 1;j <= i;j ++) if((xx[j].dd == ind.date && xx[j].mm == ind.mon)) {
if(xx[j].ty) res ++; else res --;
}
if(tot < 0) {puts("-1");return 0;}
if(ind.date == xx[i + 1].da && ind.mon == xx[i + 1].mo && i != n + 1) {
dp[tot][i] = max(dp[tot][i] , dp[tot - 1][i] + res);
if((xx[i + 1].dd == ind.date && xx[i + 1].mm == ind.mon)) {
if(xx[i + 1].ty) res ++; else res --;
}
dp[tot][i + 1] = max(dp[tot][i + 1] , dp[tot - 1][i] + res);
}
else
dp[tot][i] = max(dp[tot][i] , dp[tot - 1][i] + res);
}
tot ++;
nxt(ind);
}
ans=-1;
for(int i=1;i<=tot;i++) ans=max(ans,dp[i][n]);
if(n<=9) printf("%d\n",ans - 3);
else printf("%d\n",ans);
}
```
by functionendless @ 2017-09-09 16:27:02
讲真你不知道可以看评测吗
by 1000001001wj @ 2017-09-22 16:32:05