发现一个新方法
mathematica的函数Manipulate
支持带有参数的函数绘图然后可以调节参数。
下面的就是用来调<s>戏</s>试一个二次函数的图像。
Manipulate[
Plot[a*x^2 + b*x + c, {x, -10, 10}], {a, -.1, -3}, {b, 0, 3}, {c, 0, 3}]
<s>这高亮脚本还是自己写的</s>
效果大致是这样
mathematica的函数Manipulate
支持带有参数的函数绘图然后可以调节参数。
下面的就是用来调<s>戏</s>试一个二次函数的图像。
Manipulate[
Plot[a*x^2 + b*x + c, {x, -10, 10}], {a, -.1, -3}, {b, 0, 3}, {c, 0, 3}]
<s>这高亮脚本还是自己写的</s>
效果大致是这样
终于找到一个可以用的代码高亮插件了!
终于找到一个可以用的代码高亮插件了!
高兴的事要说两遍!
是我的错我居然天真地以为百度就能找到全部插件……
考完试后顺便改一改看起来更顺眼的配色方案吧……
在不要求输出路径的情况下只是简单的一笔画问题。小学奥数啊。
虽说咱市奥校没好好听但这还是会的。
判定条件:存在欧拉回路当且仅当奇数度的点数为2或0。
不过咱不会严格证明啊。。。要死。。。
再次膜拜欧拉神!
#include <iostream>
using namespace std;
const int maxn = 1e4 + 10;
int island[maxn] = {0};
int main()
{
int n, m;
cin>>n>>m;
while(m--)
{
int u, v;
cin>>u>>v;
island[u]++;
island[v]++;
}
int cnt = 0;
for(int i = 1; i <= n; i++)
if(island[i] & 1)
cnt++;
if(cnt == 2 || cnt == 0)
cout<<"Full"<<endl;
else
cout<<"Part"<<endl;
return 0;
}
第一题 大冒险 提交文件: adventure.pas/c/cpp 输入文件: adventure.in 输出文件: adventure.out
最近,小明又玩起了一个古老的游戏:大冒险。每个玩家在 N 个格子的环形地图上进行游戏,格子编号为 0 到 N −1。 每一个玩家控制游戏角色,从编号为 0 的格子出发,轮流掷骰子,骰子上的点数为 1 ∼ 6,代表接下来玩家将 向前移动的格子数。
注意的是,地图是环形的,所以假设现在玩家所在的格子为 x,骰子上的点数为 y,那么他将要移动到的格子 为 (x + y) mod N, a mod b 表示 a 除以 b 的余数。 另外 N 个格子中有 M 个格子 (M ≤ N −2) 上有传送门,当玩家到达目标格子且这个格子有传送门时,传送 门将立刻带玩家到另一个格子。如果传送到的格子也有传送门,玩家并不会再次被传送门传送。 玩家到达编号为 N −1 的格子就获胜。 现在小明并不关心他是否能获胜,他只想知道是否可能游戏一段时间后,进入了某个格子,这个格子无论如何 都不能到达终点。
输入格式 第一行有 1 个整数 T,表示数据组数。 接下有 T 个测试样例。 每个测试样例的第一行有 2 个整数,N、M。 接下来 M 行,每行两个整数 x,y,(x ̸= y) 表示编号为 x 的格子,有传送门直接到达编号为 y 的格子。 保证每个格子至多有一个传送门,并且编号为 0 和 N −1 的格子都没有传送门。 输出格式 对于每一个测试样例,如果可能的话,输出“YES”,否则输出“NO”。 adventure.in adventure.out 2 10 7 1 9 3 2 4 2 5 2 6 2 7 2 8 2 10 5 2 1 3 1 4 1 5 1 6 1 YES NO
数据范围 对于 40% 数据,10 ≤ N ≤ 4000
对于 100% 数据,10 ≤ N ≤ 100000,1 ≤ T ≤ 10,0 ≤ M ≤ N −2【待格式化】
双向广搜即可。
比赛时毕竟还是naive!
而且调了半个月最终还是错在变!量!名!打!反!
简直了。这是要退役了的节奏。
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream cin("adventure.in");
ofstream cout("adventure.out");
const int maxm = 1e5 + 10;
int n, m;
struct Node
{
int go;
bool can[2][2];
vector<int> back;
void init()
{
go = -1;
memset(can, false, sizeof can);
back.clear();
}
} nodes[maxm];
typedef pair<int, bool> pib;
void bfs1()
{
queue<pib> Q;
Q.push(make_pair(0, false));
while(!Q.empty())
{
pib t = Q.front(); Q.pop();
int num = t.first; bool refer = t.second;
if(num > n - 1)
continue;
if((refer && nodes[num].can[0][0]) || (!refer && nodes[num].can[0][1]))
continue;
if(refer)
nodes[num].can[0][0] = true;
else
nodes[num].can[0][1] = true;
if(refer || nodes[num].go == -1)
{
for(int i = 1; i <= 6; i++)
Q.push(make_pair(num + i, false));
}
else
{
Q.push(make_pair(nodes[num].go, true));
}
}
}
void bfs2()
{
queue<pib> Q;
Q.push(make_pair(n - 1, false));
while(!Q.empty())
{
pib t = Q.front(); Q.pop();
int num = t.first; bool refer = t.second;
if(num < 1)
continue;
if((refer && nodes[num].can[1][0]) || (!refer && nodes[num].can[1][1]))
continue;
if(refer)
nodes[num].can[1][0] = true;
else
nodes[num].can[1][1] = true;
if(!(refer || nodes[num].back.empty()))
{
for(int i = 0; i < nodes[num].back.size(); i++)
Q.push(make_pair(nodes[num].back[i], true));
}
for(int i = 1; i <= 6; i++)
Q.push(make_pair(t.first - i, false));
}
}
bool go()
{
bfs1();
bfs2();
for(int i = 1; i <= n - 1; i++)
if(!((nodes[i].can[0][0] && nodes[i].can[1][1])
|| (nodes[i].can[0][1] && nodes[i].can[1][0])
|| (nodes[i].can[0][1] && nodes[i].can[1][1])))
return false;
return true;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
if(m == 0)
{
cout<<"NO"<<endl;
continue;
}
for(int i = 0; i < n + 10; i++)
nodes[i].init();
for(int i = 0; i < m; i++)
{
int x, y;
cin>>x>>y;
nodes[x].go = y;
nodes[y].back.push_back(x);
}
if(go())
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
return 0;
}
打算去清远前清理桌面,于是发现了这个GDOI遗留下的未完成品。
最小表示法什么的,虽说有专门的算法,不过SAM用起来似乎更顺手。直接两倍原串后按字典序跑一遍就行了。
但那个神奇的算法还是找个时间研究一下吧。
RE了六次,WA了两次。
原因:变量名打错;字符串被分割称多行却无告知。
呃,几乎每次都是变量名打错而出错的呢。
#include <iostream>
#include <cstring>
using namespace std;
namespace DEL
{
template<int maxn, int sigma = 26>
class Suffix_Automaton
{
private:
struct Node
{
Node *fail;
Node *ch[sigma];
int len;
Node(){memset(ch, 0, sizeof ch);}
} *head, *tail, pool[maxn * 2];
int cnt, len;
inline int idx(char c)
{
return c - 'a';
}
public:
void init(int l)
{
//memset(&pool, 0, sizeof pool);
head = tail = &pool[0];
cnt = 1;
len = l;
}
void add(char c)
{
int id = idx(c);
Node *p = tail, *newnode = &pool[cnt++];
newnode -> len = p -> len + 1;
tail = newnode;
for(; p && !p -> ch[id]; p = p -> fail)
p -> ch[id] = newnode;
if(!p)
newnode -> fail = head;
else if(p -> len + 1 == p -> ch[id] -> len)
newnode -> fail = p -> ch[id];
else
{
Node *q = p -> ch[id], *r = &pool[cnt++];
*r = *q;
r -> len = p -> len + 1;
q -> fail = newnode -> fail = r;
for(; p && p -> ch[id] == q; p = p -> fail)
p -> ch[id] = r;
}
}
int go()
{
Node *p = head;
for(int i = 0; i < len; i++)
for(int j = 0; j < sigma; j++)
{
if(p -> ch[j])
{
p = p -> ch[j];
break;
}
}
return p -> len - len;
}
};
}
DEL::Suffix_Automaton<1000000> SAM;
int main()
{
int l;
cin>>l;
string s;
cin>>s;
string s1;
while(cin>>s1)
s += s1;
SAM.init(l);
s += s;
for(unsigned int i = 0; i < s.length(); i++)
SAM.add(s[i]);
cout<<SAM.go()<<endl;
return 0;
}