Codeforces Round #549 (Div. 1) C&D&ECodeforces Round #549 (Div. 1) C&D&E

Codeforces Round #549 (Div. 1)  C&D&E

C

把x方减去，bx+c 就是个一次函数，然后发现上方没有点的限制相当于这个直线上方没有点，所以是个凸包

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6+5;
struct Node{
	ll x,y;
	Node(ll x = 0,ll y = 0) : x(x), y(y) {}
	long double operator * (const Node b)const{
		return (long double)y*b.x - (long double)x*b.y;
	}
	Node operator - (const Node b)const{
		return Node(this->x - b.x,this->y - b.y);
	}
	bool operator < (const Node b) const {
		return x==b.x ? y<b.y : x < b.x;
	}
}t[N];
int n;
Node stk[N];int top;

int main()
{
	cin >> n;
	for(int i=1;i<=n;i++){
		ll x,y;cin >> x >> y;
		t[i] = Node(x,y-x*x);
	}
	sort(t+1,t+n+1);
	for(int i=1;i<=n;i++){
		if(t[i].x == t[i+1].x && i!=n) continue;
		while(top>=2 && 0 >= (stk[top]-stk[top-1]) * (t[i]-stk[top-1]))--top;
		stk[++top] = t[i];
	}
	cout << top-1 << endl;
	return 0;
}
           

D

关键在于对于顺序的转移，考虑如何构造出所有小于他的数。

对 x ， t = x/10 ，我们用所有的 < t 的数加上所有能够加的，再加上1 - 9 ， 然后再把t上比他小的加上去就构造出所有比它小的了，然后发现%11 = 0 ~ 10 生成的数加起来mod 11  == 0，于是只用记录%11的余数预处理转移就行了。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n;
char s[N];
int t[12][12];
typedef long long ll;
ll f[N][12];
ll ans = 0;
int main()
{
	scanf("%s",s+1);
	n = strlen(s+1);
	for(int i=0;i<=10;i++){
		int pre = i-1;pre = pre < 0 ? pre+11:pre;
		for(int digit=0;digit<i;digit++){
			t[i][digit] = 9 + pre*(pre+1)/2 + digit + 1;
			t[i][digit] %= 11;
		}
	}
	for(int i=1;i<=n;i++){
		int c = s[i]-'0';
		for(int j=c+1;j<=10;j++)
			f[i][t[j][c]] += f[i-1][j];
		if(c!=0)f[i][c]++;
		for(int j=0;j<=10;j++) ans+=f[i][j];
	}
	cout << ans << endl;
	
}
           

E

先看m=0的情况，很容易构造出每次拓展一个点根据方向换根最后成一颗树。

然后发现我们现在需要解决的就是拓展点的时候找不到边的情况。

发现只要它不能到达的点都已经在当前的树里面就可以做了，那每个没入度的分量随便选一个点。每次一个点（不是根）在树里面，要么再在这个分量取一个，要么这个分量没了把边删掉没入度的加进去就行了。

include<bits/stdc++.h>
using namespace std;

int query(int x,int y){
	printf("? %d %d\n",x,y);
	fflush(stdout);
	int ans; scanf("%d",&ans);
	return ans;
}

const int N=2e5+5;
int hed[N],from[N],to[N],nxt[N],cnt;
int deg[N];
inline void adde(int u,int v){
	++cnt;from[cnt]=u,to[cnt]=v,nxt[cnt]=hed[u];hed[u]=cnt;
}
int dfn[N],low[N],num,stk[N],top,col[N],cn;
vector<int> scc[N];
int n,m;
inline void tarjan(int x){
	dfn[x] = low[x] =++num;
	stk[++top] = x;
	for(int i=hed[x];i;i=nxt[i]){
		int v=to[i];
		if(!dfn[v]){
			tarjan(v);
			low[x] = min(low[x], low[v]);
		}else if(!col[v])low[x] = min(low[x],dfn[v]);
	}
	if(low[x]==dfn[x]){
		++cn;
		while(stk[top]!=x){
			scc[cn].push_back(stk[top]);
			col[stk[top--]] = cn;
		}
		scc[cn].push_back(stk[top]);
		col[stk[top--]] = cn;
	}
}

queue<int> Non;
int S;
vector<int> toward[N];
inline void del(int x){
	int c=col[x];
	scc[c].pop_back();
	if(scc[c].size()){
		Non.push(scc[c][scc[c].size()-1]);
	}else{
		for(size_t i=0;i<toward[c].size();i++){
			int v=toward[c][i];
			deg[v]--;
			if(deg[v]==0)Non.push(scc[v][scc[v].size()-1]);
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		adde(u,v);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=cnt;i++){
		if(col[from[i]]!=col[to[i]]){
			deg[col[to[i]]]++;
			toward[col[from[i]]].push_back(col[to[i]]);
		}
	}
	for(int i=1;i<=cn;i++)if(!deg[i]){
		Non.push(scc[i][scc[i].size()-1]);
	}
	S = Non.front();Non.pop();
	while(!Non.empty()){
		int t = Non.front(); Non.pop();
		int ret = query(S,t);
		if(ret==1){
			del(t);
		}else{
			del(S);
			S=t;
		}
	}
	cout << "! " << S << endl;
}