弱校连萌 2016 10.3
。。。sad.....
果然没睡够&起来就写题脑子完全就是不清醒的状态。。。
这个不清醒。。。主要体现在。。。。10+次。。。忘记删条件编译。。。
改着改着。。。就忘记这件事了。。。好烦啊。。。本来早就A了。。。结果又接着去改。。。
题目链接：jag2016
就水了三道题。。。。
A是个暴力。。直接O(n2)算乘积，然后再check一下合法性就好。。。尼玛wa到我怀疑人生。。。过了好久才考虑也许是不支持条件编译的问题。
/* ***********************************************
Author :111qqz
Created Time :2016年10月03日 星期一 12时37分27秒
File Name :code/weakteam/20161003/A.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <bitset>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1005;
int n;
int a[N];
int ans = -1;
int digit[20];
void check(int x)
{
ms(digit,0);
int len = 0 ;
int xx = x;
while (x)
{
digit[++len] = x;
x/=10;
}
for ( int i = len-1 ; i>=1 ; i--)
{
if (digit[i+1]-digit[i]!=-1) return;
}
ans = max(xx,ans);
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("code/in.txt","r",stdin);
#endif
cin>>n;
for ( int i = 1 ; i <= n ; i++) scanf("%d",a+i);
for ( int i = 1 ; i <= n-1 ; i++)
for ( int j = i+1; j <= n ; j++)
check(a[i]*a[j]);
printf("%d\n",ans);
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
B是bfs...我的做法是先算每个点有士兵到达的最小时间。然后公主跑到某个点的时候判断当前时间是否小于这个格子士兵到达的最小时间。
不过这样做会Tle，可以加个剪枝，就是在处理每个点有士兵到达的最小时间的时候，如果某个点存在比当前士兵到达的时间的更短的时间。。。那么这个士兵其实就没用了。。。直接不再入队。。。（同时要记得先把所有士兵位置标记一下再跑bfs）
/* ***********************************************
Author :111qqz
Created Time :2016年10月03日 星期一 13时10分37秒
File Name :code/weakteam/20161003/B.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <bitset>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=205;
int d[N][N];
char maze[N][N];
int n,m;
vector< pi >sol;
bool vis[N][N];
struct point
{
int x,y;
int d;
bool ok ()
{
if (x<0||y<0||x>=n||y>=m||vis[x][y]||maze[x][y]=='#') return false;
return true;
}
void look()
{
printf("x:%d y:%d d:%d\n",x,y,d);
}
}s,pri;
void bfs( point s)
{
ms(vis,false);
vis[s.x][s.y] = true;
d[s.x][s.y] = 0 ;
queue<point>q;
q.push(s);
while (!q.empty())
{
point pre = q.front();
q.pop();
point nxt;
for ( int i = 0 ; i < 4 ; i++)
{
nxt.x = pre.x + dx4[i];
nxt.y = pre.y + dy4[i];
if (!nxt.ok()) continue;
if (d[pre.x][pre.y]+1>=d[nxt.x][nxt.y]) continue;
vis[nxt.x][nxt.y] = true;
d[nxt.x][nxt.y] = min(d[pre.x][pre.y] + 1,d[nxt.x][nxt.y]);
q.push(nxt);
}
}
}
bool bfs2()
{
ms(vis,false);
vis[pri.x][pri.y] = true;
queue<point>q;
q.push(pri);
while (!q.empty())
{
point pre = q.front();
if (maze[pre.x][pre.y]=='%') return true;
q.pop();
point nxt;
for ( int i = 0 ; i < 4 ; i++)
{
nxt.x = pre.x + dx4[i];
nxt.y = pre.y + dy4[i];
nxt.d = pre.d + 1;
if (!nxt.ok()) continue;
if (nxt.d>=d[nxt.x][nxt.y]) continue;
vis[nxt.x][nxt.y] = true;
q.push(nxt);
}
}
return false;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
scanf("%d%d",&n,&m);
for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
ms(d,0x3f);
for ( int i = 0 ; i < n ; i++)
{
for ( int j = 0 ; j < m ; j++)
{
if (maze[i][j]=='@')
{
pri.x = i ;
pri.y = j ;
pri.d = 0;
}
if (maze[i][j]=='$')
{
sol.push_back(make_pair(i,j));
}
}
}
int siz = sol.size();
for ( int i = 0 ; i < siz ; i ++)
{
d[sol[i].fst][sol[i].sec]=0;
}
for ( int i = 0 ; i < siz; i++)
{
s.x = sol[i].fst;
s.y = sol[i].sec;
bfs(s);
}
if (bfs2())
puts("Yes");
else puts("No");
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
d题：构造。。一开始思路错了。。。以为让所有的数都是三角形数会比较优秀。。。然而当A为8的时候。。按照这个思路，答案为)()()))(((
但实际上存在更优的答案为))())(((
造成这个错误的原因是。。。忽视了每一部分之间的关联。。。以为减去一个三角形数以后就成了一个新 的问题。。。
但是实际上不是这样。。。
我们可以手写从A=6到A=10的情况。。。。规律比较显然。。。
具体写的时候我预处理了小于等于A的三角形数。。。
/* ***********************************************
Author :111qqz
Created Time :2016年10月03日 星期一 15时22分25秒
File Name :code/weakteam/20161003/D.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <bitset>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int A;
int k;
int a[N];
vector<int>ans;
void print(int x)
{
for ( int i = 1 ; i <= x; i++) printf(")");
for ( int i = 1 ; i <= x ; i++) printf("(");
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
cin>>A;
int cnt = 0 ;
for (int i = 1 ; k<=A ; i++)
{
k = i*(i+1)/2;
a[++cnt] = k;
}
int x = upper_bound(a+1,a+cnt+1,A)-a-1;
if (A==a[x])
print(x);
else
{
int delta = A-a[x];
for ( int i = 1 ; i <= delta ; i++ ) printf(")");
printf("(");
for ( int i = 1 ; i <= x+1-delta ; i++) printf(")");
for ( int i = 1 ; i <= x ; i++) printf("(");
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
剩下的题没来得及看。。。。。。。不过目测还有2道可以做（？