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;
}