总结
代码地址 | 题目地址 | 关键算法 | 难度 |
---|---|---|---|
Q1-Countdown.cpp | Countdown | 直接遍历 | 简单 |
Q2-StableWall.cpp | Stable Wall | 拓扑排序 | 简单 |
Q3-PerfectSubway.cpp | Perfect Subway | 组合数学+trik | 简单 |
Q4-Candies.cpp | Candies | 线段树 | 较难 |
Q1-Countdown
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define maxN 200000+50
// 直接遍历+判断即可
int main()
{
int num[maxN];
int t,T,N,n,K,k,temp_K;
int cnt,flag;
scanf("%d", &T);
for(t=1; t<=T; t++)
{
cnt = 0;
memset(num, 0, sizeof(num));
scanf("%d %d", &N, &K);
// 先全部输入
for(n=0; n<N; n++)
{
scanf("%d", &num[n]);
}
for(n=0; n<N; n++)
{
// 发现K值,判断是否为m-countdown
if(num[n] == K)
{
flag = 1;
temp_K = K;
// 向后遍历K个数
for(k=0; k<K; k++)
{
if(num[n+k] == temp_K)
{
temp_K = temp_K-1;
continue;
}
else
{
flag = 0;
break;
}
}
if(flag == 1)
{
cnt++;
//n = n+K;
}
}
}
printf("Case #%d: %d\n", t, cnt);
}
/* std::cout << "Hello world" << std::endl; */
return 0;
}
Q2-StableWall
/***********************************************
#
# Filename: 2020C-Q2-StableWall.cpp
#
# Author: Li Xudong - 757264690@qq.com
# Description: ---
# Create: 2020-11-12 15:08:39
# Last Modified: 2020-11-13 01:42:42
#
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <string.h>
#include <set>
using namespace std;
// 这一题其实很简单
// 题目的意思是用字母当多米诺骨牌进行堆叠,判断这个堆叠方案是否稳定,如果稳定,输出堆叠序列
// 但是字母的堆叠是有顺序的,每个字母是一次性堆好的.
// 比如,下面的一个序列:
// MM
// MF
// MM
// 如果先堆字母M,则最右上角的字母M,因为它的下面是空的(还没有堆F呢),所以M容易落下来,则是不稳定的
//
// 看到先后顺序,首先想到了拓扑排序
// 怎么建图呢?
// 从下面往上开始建立,并且一列一列建立,对于上面的例子,
// 首先第一列都是M,肯定是稳定的,无需增加边,加一个顶点M
// 对于第二列,从往上,分别是M-F-M,则需要在顶点M和顶点F之间增加一条边,之后在顶点F和顶点M之间增加一条边(其实,这时候已经有环了,是不稳定的)
// 建好拓扑图后,拓扑排序,输入节点即可,如果没有将所有节点输出,则有环,输出-1
//
#define maxN 35
// 26个顶点
#define maxP 26
// 字母矩阵
char alp[maxN][maxN];
int main()
{
int t,T,R,C;
int i,j,k;
scanf("%d", &T);
// 拓扑图
vector<int> G[maxP];
// 入度
int d[maxP];
// 拓扑排序的输出队列
queue<int> tst,ans;
// 字母集合
set<int> ss;
for(t=1; t<=T; t++)
{
scanf("%d %d", &R, &C);
memset(alp, 0, sizeof(alp));
// 拓扑图和入度数组的初始化
for(i=0; i<maxP; i++)
{
G[i].clear();
d[i] = 0;
}
for(i=0; i<R; i++)
for(j=0; j<C; j++)
{
scanf(" %c", &alp[i][j]);
ss.insert(alp[i][j]-'A');
}
// 建立拓扑图形
for(i=0; i<R-1; i++)
{
for(j=0; j<C; j++)
{
// 如果上下两个字母相同,则不添加任何边
if(alp[i][j] != alp[i+1][j])
{
G[alp[i+1][j]-'A'].push_back(alp[i][j]-'A');
d[alp[i][j]-'A']++;
}
}
}
// 建好图后, 就可以拓扑排序了
// 先添加入度为0的序列入队
for(i=0; i<maxP; i++)
if(!d[i] && ss.count(i))
tst.push(i);
while(!tst.empty())
{
// 输出入度为0的顶点,由于不知道有没有环,还不能输出
// printf("%c", tst.front()+'A');
k = tst.front();
tst.pop();
ans.push(k);
// 删除该顶点出发的边,并且对应的顶点入度-1
for(i=0; i<G[k].size(); i++)
{
d[G[k][i]]--;
// 如果为0,则加入队列
if(!d[G[k][i]])
tst.push(G[k][i]);
}
}
printf("Case #%d: ",t);
if(ans.size() == ss.size())
{
while(!ans.empty())
{
printf("%c", ans.front()+'A');
ans.pop();
}
printf("\n");
}
else
printf("-1\n");
/* printf("Case #%d: ",t); */
// 清除集合
ss.clear();
// 清除所有的顶点
for(i=0; i<maxP; i++)
G[i].clear();
// 清空tst队列、ans队列
while(!ans.empty())
ans.pop();
while(!tst.empty())
tst.pop();
}
return 0;
}
Q3-PerfectSubway
/***********************************************
#
# Filename: 2020C-Q3-PerfectSubway.cpp
#
# Author: Li Xudong - 757264690@qq.com
# Description: ---
# Create: 2020-11-13 17:42:55
# Last Modified: 2020-11-15 00:44:57
#
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <unordered_map>
// 运行: g++ 2020C-Q3-PerfectSubway-AC.cpp -std=c++11 ; ./a.out
// 貌似是以前的组合数学问题,要求求出 子集合元素和 为完全平方数的子集数量
// 比如一个数组a1到a10,
// 假设a5到a7是一个满足的子集,其和为b的平方
// 则a5+a6+a7=b*b
// 等同于sum(1,7)-sum(1,4)=b*b
// 等同于sum(1,7)-b*b = sum(1,4)
// 因此,我们需要对b依次进行遍历,看数组中是否有sum(1,4)存在,如果存在,则有满足的子集和
// 第一次用的set来做,看到别人用map AC了,尝试用map做一下
using namespace std;
const int maxN = 1e5+20;
const int inf = 1e7+20;
int sum[maxN];
unordered_map<int, int> m;
void solve()
{
int N;
int n;
int i,j,k;
long long ans=0;
int minn=0;
scanf("%d", &N);
memset(sum, 0, sizeof(sum));
m.clear();
// 存储和
for(n=1; n<=N; n++)
{
scanf("%d", &k);
sum[n] += sum[n-1]+k;
minn = min(minn, sum[n]);
}
m[0]=1;
for(i=1; i<=N; i++)
{
for(j=0; j*j<=inf; j++)
{
if(m.count(sum[i]-j*j))
{
ans += m[sum[i]-j*j];
}
if((sum[i]-j*j)<minn)
break;
}
m[sum[i]]++;
}
printf("%lld\n", ans);
}
int main()
{
int t,T;
scanf("%d", &T);
for(t=1; t<=T; t++)
{
//solve();
printf("Case #%d: ", t);
solve();
}
}
Q4-Candies
/***********************************************
♡ Filename : 2020C-Q4-Candies.cpp
♡
♡ Description : ---
♡ Author : Li Xudong
♡ Contact : 757264690@qq.com
♡ Created : 2020-12-17 09:29:13
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
// 如果直接对原数组操作,则查询操作为O(n),而更新操作复杂度为O(1)。
// 如果构建前缀和数组,则查询操作为O(1),而更新操作复杂度为O(n)。
// 因此出现了矛盾。
//
// 一个比较常用的方法就是使用线段树方法。
// 构建两个线段树:
// 假设数组元素为[t1,t2,t3,t4,t5...]
// 1.第一棵树,构建了t1,-t2,t3,-t4,t5...等元素的线段树
// 2.第二棵树,构建了1*t1, 2*(-t2), 3*t3, 4*(-t4), 5*t5...等元素的线段树
// 则每次查询的结果"Q L R"可以表示为,(第二棵树-第一棵树*(L-1)) * ((-1)^(L-1))
//
// 都是线段树的基础操作:建立树、更新树、查询树
//
const int maxn = 2e5+10;
int t[maxn];
long long tree[maxn<<2][2]; // 第一棵树tree[][0],第二棵树tree[][1]
void build_tree(int node, int start, int end)
{
if(start==end)
{
tree[node][0] = t[start];
tree[node][1] = t[start]*start;
}
else
{
int mid = (start+end)/2;
int leftnode = node*2;
int rightnode = node*2+1;
build_tree(leftnode, start, mid);
build_tree(rightnode, mid+1, end);
tree[node][0] = tree[leftnode][0] + tree[rightnode][0];
tree[node][1] = tree[leftnode][1] + tree[rightnode][1];
}
}
void update_tree(int node, int start, int end, int idx, int val)
{
if(start==end)
{
//t[idx] = val;
tree[node][0] = val;
tree[node][1] = val*start;
}
else
{
int mid = (start+end)/2;
int leftnode = node*2;
int rightnode = node*2+1;
if(idx<=mid)
{
update_tree(leftnode, start, mid, idx, val);
}
else
{
update_tree(rightnode, mid+1, end, idx, val);
}
tree[node][0] = tree[leftnode][0] + tree[rightnode][0];
tree[node][1] = tree[leftnode][1] + tree[rightnode][1];
}
}
// 查询第一棵树
long long query_tree1(int node, int start, int end, int L, int R)
{
if(L>end || R<start) return 0;
else if((start == end) || (L<=start && end<=R) ) return tree[node][0];
else{
int mid = (start+end)/2;
int leftnode = node*2;
int rightnode = node*2+1;
long long sum_left = query_tree1(leftnode, start, mid, L, R);
long long sum_right = query_tree1(rightnode, mid+1, end, L, R);
return sum_left + sum_right;
}
}
// 查询第二棵树
long long query_tree2(int node, int start, int end, int L, int R)
{
if(L>end || R<start) return 0;
else if((start == end) || (L<=start && end<=R) ) return tree[node][1];
else{
int mid = (start+end)/2;
int leftnode = node*2;
int rightnode = node*2+1;
long long sum_left = query_tree2(leftnode, start, mid, L, R);
long long sum_right = query_tree2(rightnode, mid+1, end, L, R);
return sum_left + sum_right;
}
}
void solve()
{
int N, Q;
scanf("%d %d", &N, &Q);
int i,j;
memset(t, 0, sizeof(t));
memset(tree, 0, sizeof(tree));
for(i=1; i<=N; i++)
{
scanf("%d", &t[i]);
if(!(i&1))
{
t[i] = -t[i];
}
}
build_tree(1, 1, N);
long long ans = 0;
char c;
int num1, num2;
for(i=1; i<=Q; i++)
{
scanf(" %c", &c);
if(c=='U')
{
scanf("%d %d", &num1, &num2);
if(!(num1&1)) num2 = -num2;
update_tree(1, 1, N, num1, num2);
}
else
{
scanf("%d %d", &num1, &num2);
long long sum1 = query_tree1(1, 1, N, num1, num2);
long long sum2 = query_tree2(1, 1, N, num1, num2);
sum2 = sum2-sum1*(num1-1);
if(!(num1&1)) sum2 = -sum2;
ans += sum2;
}
//printf("%lld\n", ans);
}
printf("%lld\n", ans);
}
int main()
{
int t, T;
scanf("%d", &T);
for(t=1; t<=T; t++)
{
printf("Case #%d: ", t);
solve();
}
}
0