A .Assigning Workstations
题意：给定N个人的工作时间和工作时长，我们可以假设有无数台工作机器，如果一台机器超过M时间未使用就会关闭，那么我们怎么安排机器的使用，使得需要开启机器的次数最少。
思路：贪心，维护一个时间队列q，维护一个单调队列q1； 前者表示没有使用了但还没关闭的机器队列，后者表示还在使用的机器。 那么我们每次把已经使用完的加入q，如果关闭了或者被新的人使用了就移除。 使用的新机器加入q1....
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn = 3e5 + ;
struct node
{
ll a, s;
bool operator < (const node& b)const{
return a < b.a || a == b.a && s < b.s;
}
}a[maxn];
int ans; ll n, m;
queue<int>q;
priority_queue<int>q1;
int main()
{
scanf("%lld%lld", &n, &m);
for(int i = ; i <= n; i++)
scanf("%lld%lld", &a[i].a, &a[i].s);
sort(a + , a + + n);
for(int i = ; i <= n; i++)
{
while(!q1.empty())
if(-q1.top() <= a[i].a)q.push(-q1.top()+m),q1.pop();
else break;
while(!q.empty()&&q.front()<a[i].a)q.pop();
if(!q.empty())q1.push(-a[i].a-a[i].s),q.pop();
else ans++,q1.push(-a[i].a-a[i].s);
}
printf("%d",n-ans);
return ;
}
B .Better Productivity
题意：给出N个人，现在让你分P组，每组的工作效率是最小结束时间-最大开始时间，要求每一组的效率的正数，求最大效率和。
思路： 把包含至少一个其他的分到A组；否则到B组。
A组的要么单独分到一组，要么和它包含的某一个在一组（可以反证，假设已经分好组了，现在把不是单独分组的A加进去，如果分到不是包含关系的里面去，只会把答案变小）。
分组可以用栈进行。 而不是N^2枚举，因为多个相同的时候我们可以要保留一个作为最小的一个分到B组。
然后，现在A里面的没有包含关系了，我们可以排序，排序后一定是相邻的分到同一组，这里DP即可。
枚举单独分组的A，加上dp[][]跟新最大值即可。 dp[i][j]表示前i个人分j组的最大效率和； mp[i][j]表示i到j的人分一组的效率。
（这种题一看就是排序，毕竟交集肯定是相邻的在一起最大，然后DP或者线段树啥的。但是这里按照左端点和右端点呢，显然在有包含关系的时候都不行，所以要去掉包含关系，比赛的时候想到这里了，然后就没思路了。 关键在于想到A组的人如果不单独分组的话，他可以分到合理的组，使得答案不减小。
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
pii a[maxn];int tot,cnt,ans;
int vis[maxn],dp[maxn][maxn],len[maxn],mp[maxn][maxn];
int main()
{
int N,P;
scanf("%d%d",&N,&P);
rep(i,,N) scanf("%d%d",&a[i].first,&a[i].second);
sort(a+,a+N+);
rep(i,,N)
rep(j,i+,N)
if(a[i].second>=a[j].second){ vis[i]=; break;}
rep(i,,N)
if(vis[i]) len[++tot]=a[i].second-a[i].first;
else a[++cnt]=a[i];
sort(len+,len+tot+); reverse(len+,len+tot+);
rep(i,,tot) len[i]+=len[i-]; rep(i,,cnt){
int Mx=a[i].second,Mn=a[i].first;
rep(j,i,cnt){
Mx=min(Mx,a[j].second),Mn=max(Mn,a[j].first);
mp[i][j]=Mx-Mn;
}
} memset(dp,-,sizeof(dp)); dp[][]=;
rep(i,,min(cnt,P))
rep(j,,cnt)
rep(k,,j-) {
if(mp[k+][j]>&&dp[k][i-]!=-)
dp[j][i]=max(dp[j][i],dp[k][i-]+mp[k+][j]);
} rep(i,max(P-cnt,),tot){
if(dp[cnt][P-i]>)
ans=max(ans,len[i]+dp[cnt][P-i]);
} printf("%d\n",ans);
return ;
}
C .Cleaning Pipes
#include<bits/stdc++.h>
#define pii pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const double eps = 1e-;
const double pi = 3.1415926535897 ;
struct Point
{
double x, y;
Point(double x = , double y = ):x(x), y(y){}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B){return Vector(A.x+B.x, A.y+B.y);}//向量+向量=向量；点+向量=向量
Vector operator - (Vector A, Vector B){return Vector(A.x-B.x, A.y-B.y);}//点-点=向量
bool operator < (const Point& a, const Point& b)
{
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int dcmp(double x)//三态函数,高精度判断
{
if(fabs(x) < eps)return ; else return x < ? - : ;
}
bool operator == (const Point& a, const Point& b)
{
return dcmp(a.x-b.x) == && dcmp(a.y-b.y) == ;
}
double Cross(Vector A, Vector B){return A.x*B.y - A.y*B.x;}//叉积
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2)
//判断线段a1a2和b1b2是否规范相交(在端点处相交得用下一个函数特殊判断)
{
double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1),
c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);
return dcmp(c1) * dcmp(c2) < && dcmp(c3) * dcmp(c4) < ;
}
Point a[];
int c[];
Point b[];
bool judge(int i, int j)//如果i和j相交，且交点不为两个线段的起点
{
if(b[i] == b[j])return true;
if(a[c[i]] == a[c[j]] || a[c[i]] == b[j] || b[i] == a[c[j]])return false;
return SegmentProperIntersection(a[c[i]],b[i],a[c[j]],b[j]);
} int color[];//0表示未染色 1表示白色 2表示黑色
vector<int>G[];
bool bipartite(int u)
{
for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
if(color[u] == color[v])return false;//u v颜色一样
if(!color[v])
{
color[v] = - color[u];//节点u与v染不同的颜色
if(!bipartite(v))return false;
}
}
return true;
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++)scanf("%lf%lf", &a[i].x, &a[i].y);
for(int i = ; i <= m; i++)
scanf("%d%lf%lf", &c[i], &b[i].x, &b[i].y);
for(int i = ; i <= m; i++)
for(int j = i + ; j <= m; j++)
if(judge(i, j))G[i].push_back(j),G[j].push_back(i);
bool flag = ;
for(int i = ; i <= m; i++)if(!color[i])
{
color[i] = ;
if(!bipartite(i)){flag = ;break;}
}
if(flag)puts("impossible");
else puts("possible");
return ;
}
D .Debugging
题意：题目给N，R，P。表示给出一个一定有一行bug的代码，长度为N，现在让你debug，你可以在某处加一行“输出”，时间是P； 运行一次的时间是R。（输出是表示你可以对比这里的放的答案是否符合预期）。现在稳你用最有策略，最坏情况下的时间。 N<1e6； R,P<1e9
思路：N很小，所以所有长度的答案都可以算出来，估计就是记忆化了。一开始以为要么是二分，要么用L-1行输出。WA了。然后才去想，还是应该把所有的情况都求出来，长度为L的时候 ，res=min((L+i)/i+R+i*P）；我们整数分块即可。
题目的最坏情况表示：你下一次需要去检验的长度是当前最长的一个区间块，即向上取整，所以我们用(L+i)/i
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
pii a[maxn];int tot,cnt,ans;
int vis[maxn],dp[maxn][maxn],len[maxn],mp[maxn][maxn];
int main()
{
int N,P;
scanf("%d%d",&N,&P);
rep(i,,N) scanf("%d%d",&a[i].first,&a[i].second);
sort(a+,a+N+);
rep(i,,N)
rep(j,i+,N)
if(a[i].second>=a[j].second){ vis[i]=; break;}
rep(i,,N)
if(vis[i]) len[++tot]=a[i].second-a[i].first;
else a[++cnt]=a[i];
sort(len+,len+tot+); reverse(len+,len+tot+);
rep(i,,tot) len[i]+=len[i-]; rep(i,,cnt){
int Mx=a[i].second,Mn=a[i].first;
rep(j,i,cnt){
Mx=min(Mx,a[j].second),Mn=max(Mn,a[j].first);
mp[i][j]=Mx-Mn;
}
} memset(dp,-,sizeof(dp)); dp[][]=;
rep(i,,min(cnt,P))
rep(j,,cnt)
rep(k,,j-) {
if(mp[k+][j]>&&dp[k][i-]!=-)
dp[j][i]=max(dp[j][i],dp[k][i-]+mp[k+][j]);
} rep(i,max(P-cnt,),tot){
if(dp[cnt][P-i]>)
ans=max(ans,len[i]+dp[cnt][P-i]);
} printf("%d\n",ans);
return ;
}
E .Elementary Math
题意：给你一个数 N， 然后下面有 N 对数，每对数可以进行 + - * 操作，每对数选择一个结果，是不是存在每对数选择的结果都不一样。如果是，把每对数选择的结果写下来，并记录下是什么操作，如果不行，就输出 impossible。
思路：这个题看着就是一个二分图匹配问题，看能否匹配N对。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
struct edge{
int d,nex,dat;
}e[];
int n,q[],d[],efree=,cnt,ans,fh[];
long long x[],y[],num[];char f[];
queue<int>que;
map<long long,int>ma;
map<long long,int>::iterator ii;
inline void add(int x,int y,int z){e[++efree]=(edge){y,q[x],z};q[x]=efree;}
int dfs(int x,int y){
if(x==cnt+||!y)return y;
int now,tot=;
for(int i=q[x];i;i=e[i].nex)
if(d[e[i].d]==d[x]+&&e[i].dat){
now=dfs(e[i].d,min(y,e[i].dat));
e[i].dat-=now;e[i^].dat+=now;
tot+=now;if(tot==y)return y;
}
if(!tot)d[x]=-;
return tot;
}
inline bool bfs(){
memset(d,,sizeof(d));d[]=;
que.push();
while(!que.empty()){
int x=que.front();que.pop();
for(int i=q[x];i;i=e[i].nex)
if(e[i].dat&&!d[e[i].d])d[e[i].d]=d[x]+,que.push(e[i].d);
}
return d[cnt+];
}
void dfs(int xx){
for(int i=q[xx];i;i=e[i].nex)
if(e[i].dat&&e[i].d<=n){
if(x[e[i].d]+y[e[i].d]==num[xx])fh[e[i].d]=;
else if(x[e[i].d]-y[e[i].d]==num[xx])fh[e[i].d]=;
else fh[e[i].d]=;
return;
}
}
long long ff(long long x,long long y,int z){
if(z==)return x+y;
if(z==)return x-y;
return x*y;
}
int main(){
scanf("%d",&n);cnt=n;f[]='+';f[]='-';f[]='*';
for(int i=;i<=n;i++){
add(,i,),add(i,,);
scanf("%lld%lld",x+i,y+i);
long long a=x[i],b=y[i];
if(!ma[a+b])ma[a+b]=++cnt,num[cnt]=a+b;
if(!ma[a-b])ma[a-b]=++cnt,num[cnt]=a-b;
if(!ma[a*b])ma[a*b]=++cnt,num[cnt]=a*b;
add(i,ma[a+b],),add(ma[a+b],i,);
add(i,ma[a*b],),add(ma[a*b],i,);
add(i,ma[a-b],),add(ma[a-b],i,);
}
for(ii=ma.begin();ii!=ma.end();ii++)
add((*ii).second,cnt+,),add(cnt+,(*ii).second,);
while(bfs())ans+=dfs(,);
if(ans==n){
for(int i=q[cnt+];i;i=e[i].nex)
if(e[i].dat)dfs(e[i].d);
for(int i=;i<=n;i++)printf("%lld %c %lld = %lld\n",x[i],f[fh[i]],y[i],ff(x[i],y[i],fh[i]));
}
else puts("impossible");
return ;
}
G .Guessing Camels
题意：给定三个N的排列A，B，C；问多少对数字(x,y)，在三个排列里x出现的位置在y的前面
思路：BC按照A标号，然后CDQ分治即可。(这里可以把排序的部分转化为双指针，会快一个log)
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int a[maxn],b[maxn],c[maxn],pos[maxn];
ll sum[maxn],ans; int N;
struct in{
int id,x,y;
}s[maxn];
bool cmp1(in w,in v){ return w.id<v.id;}
bool cmp2(in w,in v){ return w.x<v.x; }
void add(int x,int val)
{
while(x<=N){
sum[x]+=val;x+=(-x)&x;
}
}
int query(int x){
int res=; while(x){
res+=sum[x]; x-=(-x)&x;
} return res;
}
void solve(int L,int R)
{
if(L>=R) return ;
int Mid=(L+R)>>;
solve(L,Mid);
sort(s+L,s+R+,cmp2);
rep(i,L,R){
if(s[i].id<=Mid) add(s[i].y,);
else ans+=query(s[i].y);
}
rep(i,L,R){
if(s[i].id<=Mid) add(s[i].y,-);
}
sort(s+L,s+R+,cmp1);
solve(Mid+,R);
}
int main()
{
scanf("%d",&N);
rep(i,,N) scanf("%d",&a[i]),pos[a[i]]=i;
rep(i,,N) scanf("%d",&b[i]),b[i]=pos[b[i]],s[b[i]].x=i;
rep(i,,N) scanf("%d",&c[i]),c[i]=pos[c[i]],s[c[i]].y=i;
rep(i,,N) s[i].id=i;
solve(,N);
printf("%lld\n",ans);
return ;
}
I .Identifying Map Tiles
递推找位置：
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int dir[][] = {,,,,,,,};
ll f[];
int main()
{
string s;
cin >> s;
ll n = s.size();
ll x = dir[s[] - ''][];
ll y = dir[s[] - ''][];
x++,y++; for(int i = ; i < n; i++)
{
x = * x - , y = * y - ;
if(s[i] == '')x++;
else if(s[i] == '')y++;
else if(s[i] == '')x++,y++;
}
x--,y--;
cout<<n<<" "<<x<<" "<<y<<endl;
return ;
}
J .Jumbled Communication
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int ans[]; int main()
{
for(int i = ; i <= ; i++)ans[((i<<)&) ^ i] = i;
int n;
scanf("%d", &n);
for(int i = ; i < n; i++)
{
int x;
scanf("%d", &x);
printf("%d", ans[x]);
if(i == n - )puts("");
else putchar(' ');
}
return ;
}
K .Kitchen Combinatorics
题意: 从前菜，主菜，点心中各选一道菜，每道菜由一些原料组成，每种原料有一些不同的品种，问总共有多少种方法组成这三道菜。如果多道菜使用了相同的原料，则这些菜中的这种原料将是相同品种的，另外有一些不可以组合在一起的菜。
思路: 枚举所有可能组合，统计该组合使用不同原料的数目，将原料品种数相乘即为该组合方案数。相乘前先要用除法判断是否超过1e18
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int r,s,m,d,n,k[],b[],a[][];
bool f[][],fl[];long long ans;
int main(){
scanf("%d%d%d%d%d",&r,&s,&m,&d,&n);
for(int i=;i<=r;i++)scanf("%d",b+i);
for(int i=;i<=s+m+d;i++){
scanf("%d",k+i);
for(int j=;j<=k[i];j++)scanf("%d",a[i]+j);
}
for(int i=;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
f[x][y]=f[y][x]=;
}
for(int i=;i<=s;i++)
for(int j=;j<=m;j++)
if(!f[i][s+j])
for(int l=;l<=d;l++)
if(!f[i][l+s+m]&&!f[s+j][l+s+m]){
memset(fl,,sizeof(fl));
for(int p=;p<=k[i];p++)fl[a[i][p]]=;
for(int p=;p<=k[j+s];p++)fl[a[j+s][p]]=;
for(int p=;p<=k[l+s+m];p++)fl[a[l+s+m][p]]=;
long long now=;bool flag=;
for(int p=;p<=r;p++)
if(fl[p]){
if(now>1e18/b[p])return *puts("too many");
now*=b[p];
}
if(ans+now>1e18)return *puts("too many");
ans+=now;
}
printf("%lld",ans);
return ;
}