AtCoder Beginner Contest 173まとめ

今度の出題は変な感じがしますが...5つ作ったけど不快な感じ
C直接暴力列挙状态そしてcheck、Dは蜜汁贪心で、今もどのように证明するか分かりませんが、E差は多くありませんテンプレートの问题で、1つの点が押さえられて精度が长いです......
Fは少し逆思考を試験しましたか?直接計算がうまくいかないので、最初は1辺もなかったときの答えがいくらだったかを計算して、1本プラスするたびに答えがどれだけ減ったかを考えて、木の形dpのように見える問題は10行もしないで終わりました...確かに偶然ですが、AtCoderの出題日がだんだん頭を回転させているような気がします.
P.S.E題コードはこのblogを参考にして、このn選K積は最大でテンプレートとして記入しました.
 
A

#include
#include
#include
#include
using namespace std;
typedef long long ll;

inline int read() {
	int x=0,f=1;char c=getchar();
	while (c'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}

int main() {
	int n=read();
	if (n%1000==0) puts("0");
	else printf("%d
",1000-n%1000);
	return 0;
}

B

#include
#include
#include
#include
#include

C

#include
#include
#include
#include
using namespace std;
typedef long long ll;
int n,m,K;
inline int read() {
	int x=0,f=1;char c=getchar();
	while (c'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
char mp[7][7],tmp[7][7];
int ans;
inline void paint(int str,int stc) {
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			tmp[i][j]=mp[i][j];
	for (int i=1;i<=n;++i)
		if (str&(1<

D

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=2e5+4;
int n;
ll a[N];
inline int read() {
	int x=0,f=1;char c=getchar();
	while (c'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
inline bool cmp(int x,int y) {
	return x>y;
}
int main() {
	n=read();
	for (register int i=1;i<=n;++i) a[i]=read();
	sort(a+1,a+n+1,cmp);
	ll ans=a[1];
	int pos=2;
	for (int i=3;i<=n;++i) {
//		printf("%d %d
",a[i],a[pos]);
		ans+=a[pos];
		if (!(i&1)) ++pos;
	}
	cout<

E

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int n,k;
ll ans=1;
int l_neg=-1,l_pos=-1,r_neg=-1,r_pos=-1;
const ll M=1e9+7;
inline bool cmp(ll a, ll b) {
	return abs(a) a) {
	ll ret=1;
	for(int i = n - k; i < n; i++)
		(ret*=a[i])%=M;
	return ret;
}
inline int read() {
	int x=0,f=1;char c=getchar();
	while (c'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
int main() {
	n=read(),k=read();
	vector a(n,0);
	for (register int i=0;i0) r_pos=i;
		if (r_neg==-1&&a[i]<0) r_neg=i;
	}
	for (register int i=n-k-1;~i;--i) {
		if(l_pos==-1&&a[i]>0) l_pos=i;
		if(l_neg==-1&&a[i]<0) l_neg=i;
	}
	if (ans<0&&n>k) {
		if (r_pos==-1) {
			if (l_pos==-1) {
				ans=1;
				for (int i=0;i c1=a;
				vector c2=a;
				swap(c1[l_neg],c1[r_pos]);
				swap(c2[l_pos],c2[r_neg]);
//				ans==v_cmp(c1, c2)==true? calc(c1): calc(c2);
				ans=(abs(a[l_neg]*a[r_neg])>abs(a[l_pos]*a[r_pos]))?calc(c1):calc(c2);
			}
		}
	}
	cout<

F

#include
#include
#include
#include
using namespace std;
const int N=2e5+4;
typedef long long ll;
int n;
ll ans;
inline int read() {
	int x=0,f=1;char c=getchar();
	while (c'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}

int main() {
	n=read();
	for (register int i=1;i<=n;++i)
		ans+=1ll*i*(n-i+1);
	for (register int i=1;iv) u^=v^=u^=v;
		ans-=1ll*u*(n-v+1);
	}
	cout<