好吧，晋级了，复赛等着爬...
1001-数字游戏
大致思路就是看 “n*ave-min-max” 是否在 n-2个数的和 的范围内，重点是要保证 max>=min，要特判 n==1 和 n==2 的情况
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t, n, maxn, minn, aven;
int main()
{
scanf("%lld", &t);
while (t--)
{
scanf("%lld %lld %lld %lld",&n,&maxn,&minn,&aven);
if(minn>maxn) {
puts("no"); continue;
}
if(n==1) {
if(maxn==minn && minn==aven)
puts("yes");
else
puts("no");
}
else if(n==2) {
if((maxn+minn) == aven+aven)
puts("yes");
else
puts("no");
}
else {
ll k = n*aven-minn-maxn;
ll x = minn*(n-2);
ll y = maxn*(n-2);
if(k<=y && k>=x)
puts("yes");
else
puts("no");
}
}
return 0;
}
这个版本看上去简洁得多?
1002-网格路径
思路1：推dp方程，用LGV定理
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,dp[1010][1010];
char s[1010][1010];
ll ac(int a,int b,int c,int d)
{
memset(dp,0,sizeof(dp));
for(int i=a; i<=c; i++)
{
for(int j=b; j<=d; j++)
{
if(s[i][j]=='.')
{
if(i==a && j==b) dp[i][j]=1;
else dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[c][d];
}
int main()
{
int T;
cin>>T;
while(T--)
{
scanf("%d",&n);
for(int i=1; i<=n; i++) cin>>s[i]+1;
if(s[1][1]=='#'||s[n][n] == '#') {
printf("0\n");
continue;
}
ll t1 = ac(1, 2, n-1, n);
ll t2 = ac(2, 1, n, n-1);
ll t3 = ac(1, 2, n, n-1);
ll t4 = ac(2, 1, n-1, n);
if(t1*t2-t3*t4) printf("2\n");
else {
int flag = ac(1,1,n,n);
if(flag) printf("1\n");
else printf("0\n");
}
}
return 0;
}思路2：dfs+剪枝?
1003-虫族基地
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int T,n,m,x,y;
int main()
{
scanf("%d",&T);
for(; T--; )
{
scanf("%d%d%d%d",&n,&m,&x,&y);
int t=0;
if(x==y)
t = (n-1)/2;
else
t = (n-2+abs(y-x)) / 2;
t = min(t, x-1);
t = min(t, m-y);
t = min(t, n-1);
printf("%lld\n", 1LL*t*t);
}
}1004
prim一下或者打表
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,cnt,T;
bool b[101];
inline void ac(int step, int cur, int n) {
if(step==n) {
++cnt;
return;
}
int x = cur+step;
if(x>n)
x -= n;
if(!b[x]) {
b[x] = true;
ac(step+1, x, n);
b[x] = false;
}
x = cur-step;
if(x<=0)
x += n;
if(!b[x]) {
b[x] = true;
ac(step+1, x, n);
b[x] = false;
}
}
int main()
{
scanf("%d", &T);
for (; T--; )
{
scanf("%d", &n);
cnt = 0;
memset(b, false, sizeof(b));
b[1] = true;
ac(1,1,n);
printf("%d\n", cnt);
}
}1005-怀旧游戏
把 必胜态 和 必败态 搜出来，剩余的都是tie
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int f[11][11][11][11],c[10001][4],b[11][11][11][11];
int T,a1,a2,b1,b2;
struct node {int a1, a2, b1, b2;};
vector<node> a[11][11][11][11];
int soso(int a1, int a2, int b1, int b2) {
printf("%d %d %d %d %d\n", a1, a2, b1, b2, f[a1][a2][b1][b2]);
if (f[a1][a2][b1][b2])
return f[a1][a2][b1][b2];
if (!b1 || !b2)
f[a1][a2][b1][b2] = 2;
else {
int cnt = 0;
cnt += soso(b1, b2, (a1 + b1) % 10, a2);
cnt += soso(b1, b2, (a1 + b2) % 10, a2);
cnt += soso(b1, b2, (a1 + a2) % 10, a2);
cnt += soso(b1, b2, a1, (a2 + b1) % 10);
cnt += soso(b1, b2, a1, (a2 + b2) % 10);
cnt += soso(b1, b2, a1, (a2 + a1) % 10);
if (cnt == 6)
f[a1][a2][b1][b2] = 2;
else
f[a1][a2][b1][b2] = 1;
}
return f[a1][a2][b1][b2];
}
int main()
{
for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
for(int k=1; k<=9; k++)
for(int l=1; l<=9; l++) {
node res;
res.a1 = i; res.a2 = j;
res.b1 = k; res.b2 = l;
a[k][l][(i + j) % 10][j].push_back(res);
a[k][l][(i + k) % 10][j].push_back(res);
a[k][l][(i + l) % 10][j].push_back(res);
a[k][l][i][(j + i) % 10].push_back(res);
a[k][l][i][(j + k) % 10].push_back(res);
a[k][l][i][(j + l) % 10].push_back(res);
}
memset(f, 0, sizeof(f));
int head = 0;
for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
for(int k=1; k<=9; k++) {
f[i][j][k][0] = 2;
c[++head][0]=i; c[head][1]=j;
c[head][2]=k; c[head][3]=0;
f[i][j][0][k]=2;
c[++head][0]=i; c[head][1]=j;
c[head][2]=0; c[head][3]=k;
}
for(int l=1; l<=head; l++) {
int a1=c[l][0], a2=c[l][1], b1=c[l][2], b2=c[l][3];
int v = f[a1][a2][b1][b2];
if(v==2) {
for(auto i : a[a1][a2][b1][b2])
if (!f[i.a1][i.a2][i.b1][i.b2]) {
f[i.a1][i.a2][i.b1][i.b2] = 1;
c[++head][0] = i.a1; c[head][1] = i.a2;
c[head][2] = i.b1; c[head][3] = i.b2;
}
}
else {
for(auto i : a[a1][a2][b1][b2])
if (!f[i.a1][i.a2][i.b1][i.b2]
&& ++b[i.a1][i.a2][i.b1][i.b2] == 6) {
f[i.a1][i.a2][i.b1][i.b2] = 2;
c[++head][0] = i.a1; c[head][1] = i.a2;
c[head][2] = i.b1; c[head][3] = i.b2;
}
}
}
scanf("%d", &T);
for(; T--; ) {
scanf("%d%d%d%d",&a1,&a2,&b1,&b2);
if(f[a1][a2][b1][b2] == 1)
printf("Alice\n");
else
if(f[a1][a2][b1][b2] == 2)
printf("Bob\n");
else
printf("Tie\n");
}
return 0;
}