1011 Fliping game
一道简单的博弈，题目给了我们一个n*m的方阵，要求每次选择一个正面向上的硬币然后将从这个硬币到(n,m)之间的所有硬币翻面。谁最后找不到能翻的硬币谁就输。
因为无论怎么翻都要翻最后一个，所以当最后一个是正面的时候你就获得了必胜的能力，因为无论你怎么翻你都有最后那个硬币可以翻，因此一个简单判断就可以了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int s[105][105];
int n,m;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&s[i][j]);
}
}
if(s[n-1][m-1] == 0)
printf("Bob\n");
else
printf("Alice\n");
}
return 0;
}
1008 Hehe
一道简单的DP记录hehe的数量然后进行dp运算就行了。
因为互相之间差值是斐波那契数列开了一个数组存差指，表示效果不错^_^
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define maxn 2005
#define MOD 10007
#define INF 0xfffffff
char s[12000];
int f[6000];
void get()
{
f[1]=1;
f[2]=2;
for(int i=3; i<=6000; i++)
f[i]=(f[i-1]+f[i-2])%MOD;
}
int main()
{
get();
int t,counter = 1;
scanf("%d",&t);
getchar();
while(t--)
{
scanf("%s",s);
int l=strlen(s);
int ans=1;
int al=0;
for(int i=0; i<=l-4; i++)
{
if(s[i] == 'h' && s[i+1] == 'e')
{
int j = i+2;
int sum = 1;
while(s[j] == 'h'&&s[j+1] == 'e')
{
sum++;
j+=2;
}
if(sum >= 2)
{
al++;
ans = (f[sum] * ans)%MOD;
}
i = j-1;
}
}
printf("Case %d: %d\n",counter++,ans);
}
return 0;
}
1001 Palindrome subsequence
比赛时当时看完就感觉是区间DP，立马一通写，可是在去重的时候却出现了问题，老是想着加法的方式结果每次去重都是大幅的消耗时间，最后各种TLE，看了其他大牛的结题报告之后才发现原来可以直接减来去重，当时就囧了。。
还是思路不够广啊T_T
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
char s[1005];
int l;
int dp[1005][1005];
int main()
{
int t,counter = 0;
scanf("%d",&t);
getchar();
while(t--)
{
counter++;
gets(s);
l = strlen(s);
memset(dp,0,sizeof(dp));
for(int i = 0; i < l; i ++)
{
dp[i][i] = 1;
}
for(int i = 2; i <= l; i ++)
{
for(int j = 0; j + i - 1 < l; j ++)
{
int a = j;
int b = j + i - 1;
if(s[a] == s[b])
{
dp[a][b] ++;
}
else
{
if(a + 1 <= b - 1)
{
dp[a][b] -= dp[a+1][b-1];
}
}
dp[a][b] += dp[a + 1][b] + dp[a][b-1];
dp[a][b] %= 10007;
}
}
printf("Case %d: %d\n",counter,(dp[0][l-1]+10007)%10007);
}
return 0;
}
1004Strongly connected
题目以强连通为名，自然做法也与强连通相关，可怜我还兴致勃勃的推规律，真想挖个坑把自己埋了T_T
不过嘛，规律的式子还是对的，就是对象偏了，即假定现在是n个点m条边，我们求出最小强连通分量为h（要求是出入度不全为0的强连通图）
我们可以求出最后的答案ans = n * (n - 1) - h * (n - h) - m
最初没想到出入度的问题，纠结了好久，后来写好后也是各种判断，时间效率很差，但是至少能过了感觉很开心^_^
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define maxn 1000005
struct node
{
int u,v,next;
} edge[1000005];
int head[1000005];
int pos;
int n,m;
int num[maxn];
bool in[maxn];
bool out[maxn];
inline void RD(int &ret)
{
char c;
do
{
c = getchar();
}
while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
void insert() //创建有向图
{
int x,y;
for(int i=0; i<m; i++)
{
RD(x);
RD(y);
edge[pos].u = x;
edge[pos].v = y;
edge[pos].next = head[x];
head[x] = pos;
pos++;
}
}
int dfsn[maxn];
bool used[maxn];
int low[maxn];
int stack[maxn];
int scc[maxn];
int front;
int number;
int pre;
bool Instack[maxn];
void dfs(int now) //DFS缩点形成多个小的强连通图
{
front++;
stack[front] = now;
used[now] = 1;
dfsn[now] = low[now] = pre;
pre++;
Instack[now] = 1;
for(int i = head[now]; i; i = edge[i].next) //搜到为0，即已经不存在前置节点结束
{
int v = edge[i].v;
if(used[v] == 1) //所搜点已被使用的话则表示该点对应强连通图已被访问
{
if(Instack[v] == 1) //表示是此强连通图的记录点
low[now] = min(low[now],dfsn[v]);
continue;
}
dfs(v); //未找到对应位置需要继续DFS查找
low[now] = min(low[now],low[v]);
}
if(low[now] == dfsn[now])//找到的强连通存在重叠需要特判，确定强连通的大小
{
number++;
int mark;
do
{
mark=stack[front--];
scc[mark]=number;
Instack[mark]=false;
}
while(mark!=now);
}
}
void init()//输入内容初始化
{
memset(dfsn,0,sizeof(dfsn));
memset(low,0,sizeof(low));
memset(used,0,sizeof(used));
memset(Instack,0,sizeof(Instack));
pre=1;
number=0;
memset(head,0,sizeof(head));
pos=1;
}
void init2()//确定能分出两个全连通图后对出度入度初始化
{
memset(num,0,sizeof(num));
for(int i=1; i<=n; i++)
num[scc[i]]++;
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
}
int main()
{
int t,counter = 1;
RD(t);
while(t--)
{
RD(n);
RD(m);
init();
insert();
for(int i=1; i<=n; i++)
{
if(used[i] == 0)
{
front = -1;
dfs(i);
}
}
if(number == 1)//判断是否整体成强连通
{
printf("Case %d: -1\n",counter++);
continue;
}//没有整体强连通则存在解，开始求最小强连通大小
init2();
for(int i=1; i<pos; i++) //pos为目前已有的强连通的数量，对所有的强连通图进行计算
{
int x=edge[i].u;
int y=edge[i].v;
x=scc[x];
y=scc[y];
if(x != y)//不相等时存在出入度，变为1
{
in[y]=1;
out[x]=1;
}
}
int h = maxn;
for(int i=1; i<=number; i++)
if(in[i] == 0||out[i] == 0)//判断出入度确定是否可用
h=min(h,num[i]);
int ans = n * (n - 1) - h * (n - h) - m;//根据找出的最小强连通计算答案
printf("Case %d: %d\n",counter++,ans);
}
return 0;
}
1007Group
题目要我们求在特定区域内存在的互相之间数字相邻的朋友的组数。
因为是10^5的数据，10^5的询问，在线写法几乎必爆，所以要改成用线段树或者树状数组进行离线处理，修改后就是简单的改改中间判断
很容易就能写出来了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define maxn 100005
int n,m;
int s[maxn];
int a[maxn];
int ss1[maxn];
int ans[maxn];
int lowbit(int x)
{
return x&(-x);
}
void add(int i,int val)
{
while(i <= n)
{
s[i] += val;
i += lowbit(i);
}
}
int sum(int i)
{
int sum = 0;
while(i > 0)
{
sum += s[i];
i -= lowbit(i);
}
return sum;
}
struct node
{
int l,r;
int index;
}tt[maxn];
bool cmp(node x,node y)
{
return x.l < y.l;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(s,0,sizeof(s));
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
ss1[a[i]]=i;
}
ss1[0] = maxn;
ss1[n+1] = maxn;
for(int i = 1;i <= n;i++)
{
if(i < ss1[a[i]-1] && i < ss1[a[i]+1])
add(i,1);
else if(i > ss1[a[i]-1] && i > ss1[a[i]+1])
add(i,-1);
}
for(int i = 0;i < m;i++)
{
scanf("%d%d",&tt[i].l,&tt[i].r);
tt[i].index = i;
}
sort(tt,tt+m,cmp);
int i = 1;
int j = 0;
while(j < m)
{
while(i <= n && i < tt[j].l)
{
if(i > ss1[a[i]-1] && i > ss1[a[i]+1])
add(i,-1);
else if(i < ss1[a[i]-1] && i < ss1[a[i]+1])
{
int Min = min(ss1[a[i]-1],ss1[a[i]+1]);
int Max = max(ss1[a[i]-1],ss1[a[i]+1]);
add(i,-1);
add(Min,1);
add(Max,1);
}
else if(i < ss1[a[i]-1])
{
add(i,-1);
add(ss1[a[i]-1],1);
}
else
{
add(i,-1);
add(ss1[a[i]+1],1);
}
i++;
}
while( j < m && tt[j].l <= i)
{
ans[tt[j].index]= sum(tt[j].r);
j++;
}
}
for(int i = 0;i < m;i++)
printf("%d\n",ans[i]);
}
return 0;
}
1003Swipe Bo
冰面行走找出口的大模拟，情况略多，需要慢慢处理，整理好了再发上来^_^