Codeforces Round #264 (Div. 2)

2022-07-11 21:17:52

http://codeforces.com/contest/463

这场是我人生第一场cf啊。。

悲剧处处是啊。

首先，看不懂题，完全理解不了啊。都是wa了好几次才过的

所以a和b这两sb题我做了1个小时！

然后c这题我用cin。。。。。。。悲剧

因为我听说cf评测机很快！！

rating掉了73，1300名啊，如果c没tle。。。。就到300名了。。。以后一定要小心！小心！小心！

悲剧

（太急打出来的代码不是很优美）

题意：给你n个物品及他们的价格，美元加上美分，然后你有s美元，问买一种且一个所剩最大美分为多少（去掉美元）

直接判这种物品是否可行然后用100减去（总钱价格）mod100.。。。。找个最大的就完了

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=105;

int x[N], y[N], sum[N], s, can[N];

int main() {

	int n, s, maxi=-(~0u>>1);

	cin >> n >> s;

	for1(i, 1, n) { cin >> x[i] >> y[i]; if(x[i]*100+y[i]<=s*100) can[i]=1; }

	s*=100;

	int flag=0;

	for1(i, 1, n) {

		if(!can[i]) continue;

		flag=1;

		maxi=max(maxi, (100-y[i])%100);

	}

	if(!flag) maxi=-1;

	cout << maxi << endl;

	return 0;

}

给你个初始能量，从1塔爬到n塔，初始高度为0，每爬一个塔就要耗费h[k]-h[k+1]，当然是正的就可以补能量，负就就减能量，要求每一个塔的能量都不能负。求初始能量最小的答案。

输出最高的即可。。。因为不是最高的积累的能量是不可能爬到最高的。所以。。。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=100005;

int a[N], n;

int main() {

	cin >> n;

	for1(i, 1, n) cin >> a[i];

	int ans=-(~0u>>1);

	for1(i, 1, n) ans=max(a[i], ans);

	cout << ans;

	return 0;

}

放2个象到n×n的棋盘上，攻击范围为两条斜线，且斜线不能有格子重叠，将所有在斜线上的格子的和累加起来就是一个答案，求最大的答案。

不能重叠显然要黑白染色，一个象在黑，一个象在白，自己画图。然后预处理每条斜线的和，然后n^2扫一遍就行了。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const long long getint() { long long r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=2005, oo=~0u>>1;

typedef long long ll;

ll mp[N][N], lft[N+N], rgh[N+N];

int n;

int main() {

	cin >> n;

	for1(i, 1, n) for1(j, 1, n) read(mp[i][j]);

	for1(i, 1, n) for1(j, 1, n) {

		lft[i+j]+=mp[i][j];

		rgh[n+(i-j)]+=mp[i][j];

	}

	int xx=-1, yy=-1, xxx=-1, yyy=-1;

	ll now1=-oo, now2=-oo;

	for1(i, 1, n) for1(j, 1, n) {

		if((i+j)%2) { //black

			if(xx==-1 || (lft[i+j]-mp[i][j]+rgh[n+i-j])>now1) {

				xx=i; yy=j;

				now1=(lft[i+j]-mp[i][j]+rgh[n+i-j]);

			}

		}

		else {

			if(xxx==-1 || (lft[i+j]-mp[i][j]+rgh[n+i-j])>now2) {

				xxx=i; yyy=j;

				now2=(lft[i+j]-mp[i][j]+rgh[n+i-j]);

			}

		}

	}

	cout << now1+now2 << endl;

	cout << xxx << " " << yyy << " " << xx << " " << yy <<endl;

	return 0;

}

D.不会，有时间去看看

dp。。。

题意：给你1-n的排列组成的k个串，求lcs

一开始不会啊。

我们设状态d[i]表示第一行第i个组成的lcs的最大长度。

我们来想怎么转移呢。。

我们可以找到所有在i位置的数，只要判断他们都是不是都在第一行前面i个的某一个数的右边，

然后更新。

也就是说

d[i]=max(d[i], d[j]+1) j<i 当所有的 pos[a[k][i]]>pos[a[k][j]]

只要注意我的定义是第一行的就行了。

然后取所有d[i]最大的即可

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=1005;

int a[N][N], d[N], pos[N][N];

int n, m;

bool check(int x, int y) {

	for1(i, 1, m) if(pos[i][x]<pos[i][y]) return false;

	return true;

}

int main() {

	read(n); read(m);

	int ans=-1;

	for1(i, 1, m) for1(j, 1, n) {

		read(a[i][j]);

		pos[i][a[i][j]]=j;

	}

	for1(i, 1, n) rep(j, i) if(check(a[1][i], a[1][j])) d[i]=max(d[i], d[j]+1);

	for1(i, 1, n) ans=max(ans, d[i]);

	print(ans);

	return 0;

}

E.没看，有时间去看看。

听说暴力可以过。。。

正解就是dfs+分解质因数，因为修改操作不超过50，所以复杂度为O(nsqrt(a))~O(1)

gcd不等于1说明他们没有相同的质因数，所以我们只要存个质因数的链，找到这个点所有质因数的最大的祖先，就是了。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

#define rdm(x) for(int i=ihead[x]; i; i=e[i].next)

#define pb push_back

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

typedef vector<int> vin;

typedef vin::iterator vii;

const int N=100001;

vin pm[N*10*2];

int ihead[N], w[N], cnt, f[N], n, q, dep[N];

struct ED { int to, next; }e[N*2];

inline void add(const int &u, const int &v) {

	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;

	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;

}

void dfs1(const int &x, const int &ff) {

	dep[x]=dep[ff]+1;

	rdm(x) if(ff!=e[i].to) dfs1(e[i].to, x);

}

void dfs(const int &x, const int &ff) {

	vin y;

	int t=w[x], fa=-1, upd=-1;

	for(int i=2; i*i<=t; ++i)

		if(!(t%i)) {

			if(pm[i].size()) if(dep[pm[i].back()]>fa) fa=dep[upd=pm[i].back()];

			y.pb(i); pm[i].pb(x);

			while(!(t%i)) t/=i;

		}

	if(t!=1) {

		if(pm[t].size()) if(dep[pm[t].back()]>fa) fa=dep[upd=pm[t].back()];

		y.pb(t); pm[t].pb(x);

	}

	f[x]=upd;

	rdm(x) if(ff!=e[i].to) dfs(e[i].to, x);

	for(vii it=y.begin(); it!=y.end(); ++it) pm[*it].pop_back();

}

int main() {

	read(n); read(q);

	for1(i, 1, n) read(w[i]);

	for2(i, 1, n) add(getint(), getint());

	dfs1(1, 0); dfs(1, 0);

	int a, b;

	while(q--) {

		read(a); read(b);

		if(a==1) printf("%d\n", f[b]);

		else {

			read(a);

			w[b]=a;

			dfs(1, 0);

		}

	}

	return 0;

}

预处理筛素数版（快了3000ms。。。）

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

#define rdm(x) for(int i=ihead[x]; i; i=e[i].next)

#define pb push_back

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

typedef vector<int> vin;

typedef vin::iterator vii;

const int N=100001, A=N*10*2;

vin pm[N*2];

int ihead[N], w[N], cnt, f[N], n, q, dep[N], prime[N*2], pos[A], pcnt;

bool notprime[A+10];

struct ED { int to, next; }e[N*2];

inline void add(const int &u, const int &v) {

	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;

	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;

}

void init() {

	for1(i, 2, A) {

		if(!notprime[i]) prime[pcnt++]=i, pos[i]=pcnt-1;

		for(int j=0; j<pcnt && i*prime[j]<=A; ++j) {

			notprime[i*prime[j]]=1;

			if(i%prime[j]==0) break;

		}

	}

}

void dfs1(const int &x, const int &ff) {

	dep[x]=dep[ff]+1;

	rdm(x) if(ff!=e[i].to) dfs1(e[i].to, x);

}

void dfs(const int &x, const int &ff) {

	vin y;

	int t=w[x], fa=-1, upd=-1;

	for(int i=0; prime[i]*prime[i]<=t; ++i)

		if(!(t%prime[i])) {

			int p=prime[i];

			if(pm[i].size()) if(dep[pm[i].back()]>fa) fa=dep[upd=pm[i].back()];

			y.pb(i); pm[i].pb(x);

			while(!(t%p)) t/=p;

		}

	if(t!=1) {

		if(pm[pos[t]].size()) if(dep[pm[pos[t]].back()]>fa) fa=dep[upd=pm[pos[t]].back()];

		y.pb(pos[t]); pm[pos[t]].pb(x);

	}

	f[x]=upd;

	rdm(x) if(ff!=e[i].to) dfs(e[i].to, x);

	for(vii it=y.begin(); it!=y.end(); ++it) pm[*it].pop_back();

}

int main() {

	read(n); read(q);

	init();

	for1(i, 1, n) read(w[i]);

	for2(i, 1, n) add(getint(), getint());

	dfs1(1, 0); dfs(1, 0);

	int a, b;

	while(q--) {

		read(a); read(b);

		if(a==1) printf("%d\n", f[b]);

		else {

			read(a);

			w[b]=a;

			dfs(1, 0);

		}

	}

	return 0;

}

码农公寓

相关文章