SGU 404
题意：。。
收获：取模
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e2+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int main(){ string s[maxn]; int n,m; cin>>n>>m; rep(i,1,m+1) cin>>s[i]; cout<<s[n%m==0?m:n%m]; return 0; }
SGU 404
题意：给你n个人，每个人都有si和bi，两个人会打架（si>=sj&&bi<=bj || si<=sj&&bi>=bj）,然后让你邀请最多的人数
里面的所有人都不能打架
收获：反过来想，就是两个人能同时出现的就是其中一个人的s和b都严格大于另一个人的s和b，那我们排完序之后就是
一个lis的问题了
下面是一个我wa了很久的代码，
反例：
5
1 1
2 9
3 4
5 5
1 1
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e5+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int n; struct P{ int s,b,id; bool operator <(const P& c) const{ if(s==c.s) return b>c.b; return s<c.s; } }p[maxn]; int g[maxn],pre[maxn]; void init(){ mt(g,0);mt(pre,-1);g[0] = -1; } void output(int x){ if(pre[x]==-1){ printf("%d",p[x].id); return; } output(pre[x]); printf(" %d",p[x].id); } int main(){ init(); scanf("%d",&n); rep(i,1,n+1) scanf("%d%d",&p[i].s,&p[i].b),p[i].id = i; sort(p+1,p+n+1); int ans = 0; rep(i,1,n+1){ int l = 0,r = ans,pos = -1; while(l <= r){ //在前面找出找到第一个大于等于当前的b的点 int mid = (l + r) >> 1; if(p[i].b > p[g[mid]].b) l = mid + 1; else pos = mid,r = mid - 1; } if(pos == -1) ans++,pos = ans; pre[i] = g[pos - 1]; if(p[i].s <= p[g[pos]].s || g[pos] == 0) g[pos] = i; } printf("%d ",ans); output(g[ans]); return 0; }
因为s已经是递增的了，那么后面的s肯定是大于等于前面的了，那我们只要让每个s对应的b最小，这样后面的才更容易拼起来
AC代码：
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e5+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int n; struct P{ int s,b,id; bool operator <(const P& c) const{ if(s==c.s) return b>c.b; return s<c.s; } }p[maxn]; int g[maxn],pre[maxn]; void init(){ mt(g,0);mt(pre,-1);g[0] = -1; } void output(int x){ if(pre[x]==-1){ printf("%d",p[x].id); return; } output(pre[x]); printf(" %d",p[x].id); } int main(){ init(); scanf("%d",&n); rep(i,1,n+1) scanf("%d%d",&p[i].s,&p[i].b),p[i].id = i; sort(p+1,p+n+1); int ans = 0; rep(i,1,n+1){ int l = 0, r = ans, pos = -1; while(l <= r){ //在前面找出找到第一个大于等于当前的b的点 int mid = (l + r) >> 1; if(p[i].b > p[g[mid]].b) l = mid + 1; else pos = mid,r = mid - 1; } if(pos==-1) ans++, pos = ans; pre[i] = g[pos - 1]; if(p[i].b < p[g[pos]].b || g[pos] == 0) g[pos] = i; } printf("%d ",ans); output(g[ans]); return 0; }