ACLJW-CSDN博客

原创本博客已搬家到博客园，不会再更新

CSDN广告太多，用户体验太差，本博客已搬家到博客园（https://www.cnblogs.com/JingwangLi/），CSDN不会再更新了。

2019-01-11 10:24:47 244

原创 12113:Overlapping Squares

Overlapping Squares我的思路：可以根据所给图形计算出图形中包含的方块的个数以及它们各自的位置，方块可以根据某一个角点的位置来确定，具体方法见 count() 函数。方块确定之后，图形的各种变化就取决于方块们的不同放置顺序了，枚举所有排列，进行模拟，看看模拟结果里面有没有所给图形即可。思路没什么问题，代码了检查了好多遍，但是一直WA，暂时还没发现问题，再想想吧。#in...

2018-12-29 15:48:37 226

原创 211:The Domino Effect

The Domino Effect回溯加剪枝。只需DFS右、下两个方向即可，可以一行一行来。弄完一行之后看下该行所有数字是否都配对了，否则剪枝。还是得细心，两个 cnt 认错了找了大半天 bug 。。。#include<bits/stdc++.h>using namespace std;const int n = 7;int cnt;int dx[] = {1, 0}...

2018-12-16 23:41:35 255

原创 225:Golygons

Golygons回溯加剪枝。某个方向可走的条件是此方向上没有障碍物挡道，还有一点容易被忽视的就是不能落到之前到过的点上！！！最重要的剪枝就是每走一步就判断一下剩下的步数是否有可能回到原点，还有就是如果提前到达原点也要剪掉。#include<bits/stdc++.h>using namespace std;const int maxn = 50 + 5;int T, n...

2018-12-13 23:34:23 110

原创 208:Firetruck

Firetruck回溯即可，不过要注意先判断是否可以到达着火点，如果到不了那就没必要回溯了，可能给的数据比较坑，到不了的数据比较多，不判断的话会超时。还有就是输出的格式和样例给的竟然不一样，真是醉了。#include<bits/stdc++.h>using namespace std;const int maxn = 25;int t, n, cnt2;int vis...

2018-12-11 17:09:21 150

原创 1601:The Morning after Halloween（经典）

The Morning after Halloween直接BFS会超时，题目中提示过墙壁很多，那么可以将所有的空格提取出来做张图，然后记录每个空格周围的邻居，这样就不用每次都判断能不能走了。优化的话可以使用双向BFS，从每次正向（从开始位置搜索）搜索一次，反向（从目标位置搜索）搜索一次，如果有相同状态则找到最短路径。BFS（800ms）:#include<bits/stdc++...

2018-12-05 22:26:49 353

原创 10603:Fill

Fill#include<bits/stdc++.h>using namespace std;const int maxn = 200 + 5;int T, a, b, c, d;struct node{ int v[3], dist; bool operator < (const node& rhs) const{ retu...

2018-12-03 23:32:32 153

原创 1073D. Berland Fair

1073D. Berland Fair每次先走一圈，计算出可以购买的糖果的总价格 c 和总个数 t，然后 cnt += t*(T/c) T %= c，循环至无糖果可买。时间复杂度计算如下：#include<bits/stdc++.h>using namespace std;const int maxn = 200000 + 5;typedef long lon...

2018-10-31 23:54:20 118

原创 1073C. Vasya and Robot

1073C. Vasya and Robot注意如果 d 和 n 奇偶性不一致则是不可能到达的，因为机器人每移动一步，其坐标之和的奇偶性就会发生变化。#include<bits/stdc++.h>using namespace std;typedef pair<int,int>P;const int maxn = 200000 + 5;int n,x,...

2018-10-31 22:39:41 150

原创 1073B. Vasya and Books

1073B. Vasya and Books#include<bits/stdc++.h>using namespace std;const int maxn = 2*100000 + 5;int n,s[maxn],t[maxn],vis[maxn],res[maxn];int main(){ // freopen("data.in","r",stdin);...

2018-10-29 22:33:47 297

原创 1073A. Diverse Substring

1073A. Diverse Substring只要不是一串完全相同的字母就是 YES，因为至少有一个长度为2的子串是 diverse 的。傻傻地测试了所有的子串。。

2018-10-29 22:30:37 179

原创 1354:Mobile Computing

Mobile Computing枚举二叉树然后计算其宽度即可，每次枚举两个节点构造一个父节点，计算宽度时需要注意的是每棵树的左节点的右边缘可能超过其右子树的左边缘，反之亦然。#include<bits/stdc++.h>using namespace std;const int maxn = 12;int n,s,idx,w[maxn],vis[maxn];doubl...

2018-10-26 17:37:09 121

原创 16. 3Sum Closest

16. 3Sum Closest和之前3Sum那道题思路一样，刚开始想的是不用每次计算误差，只需要在小于目标和大于目标的转折点出计算两次然后临界的时候计算一次即可，可是实际上和每次都计算误差速度一样的。。。class Solution {public: int threeSumClosest(vector<int>& nums, int target) {...

2018-09-24 17:20:36 88

原创 8. String to Integer (atoi)

8. String to Integer (atoi)class Solution {public: int myAtoi(string str) { int Max = (1<<31)-1, Min = -1<<31; int i = 0; int minus = 1; while(str[i...

2018-09-20 21:06:56 87

原创 15. 3Sum

15. 3Sumclass Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<vector<int>> res; ...

2018-09-08 23:57:19 87

原创 11853:Paintball

Paintball这个题可以看作是图上有很多圆形禁区，如果直接考虑是否可以从左边走到右边似乎有些无从下手，其实可以这样考虑，把整个方形区域看作水面，把禁区看作小岛，如果可以从上边沿着这些小岛走到下边的话，就说明方形区域被禁区整个隔断了，那么就不能从左边走到右边，这样一来DFS即可。（思路来自紫书）至于最北的位置，只需要在DFS的时候计算当前禁区与左右边缘的下交点，不断更新坐标值即可。因为我...

2018-08-29 00:32:03 160

原创 11. Container With Most Water

11. Container With Most Water设置两个指针i j ，分别指向首尾两块板，然后向中间移动，那么宽度变小的情况下为了增大面积只有让高度变大，所以每次移动所指板较低的指针，然后计算面积，重复以上过程。int max(int a,int b){ return a > b ? a : b;}int maxArea(int* height, int he...

2018-08-27 12:30:35 103

原创 14. Longest Common Prefix

14. Longest Common Prefixchar s[100000];int min(int a,int b){ return a < b ? a : b;}char* longestCommonPrefix(char** strs, int strsSize) { int len = 10000,cnt = 0; for(int i = 0;i...

2018-08-26 23:47:05 106

原创 12. Integer to Roman

12. Integer to Romanchar s[100];char* intToRoman(int num) { char rs[] = "MDCLXVI"; int ts[] = { 1000,500,100,50,10,5,1 }; int cnt = 0; while(num){ int i = 0; while(...

2018-08-26 23:32:36 93

原创 13. Roman to Integer

13. Roman to Integerint romanToInt(char* s) { int dic[26]; dic['I'-'A'] = 1; dic['V'-'A'] = 5; dic['X'-'A'] = 10; dic['L'-'A'] = 50; dic['C'-'A'] = 100; dic['D'-'A'] = ...

2018-08-26 22:32:08 346

原创 673:Parentheses Balance

Parentheses Balance之前脑子可能坏掉了。。。简单的栈的应用，要注意的一个地方是一定要用 fgets ，因为如果是空串的话 scanf 会直接读下一行。#include<bits/stdc++.h>using namespace std;const int maxn = 128 + 5;int n;char s[maxn];int main(){...

2018-08-21 16:21:32 451

原创 10410:Tree Reconstruction

Tree Reconstruction#include<bits/stdc++.h>using namespace std;const int maxn = 1000 + 5;int n,x,root;int pos[maxn];vector<int>A[maxn];int main(){ // freopen("data.in","r",stdi...

2018-08-20 23:12:59 255

原创 140:Bandwidth

Bandwidth注意节点不一定是按字母表顺序从前到后用的，也有可能是A C 却没用B，因为这个TLE了好几次。。#include<bits/stdc++.h>using namespace std;const int maxn = 26;int L,w;char s[100];int seq[maxn],vis[maxn],res[maxn],num[maxn],...

2018-08-18 22:47:48 134

原创 129:Krypton Factor

Krypton Factor注意 && 别写成 & 了。。。#include<bits/stdc++.h>using namespace std;const int maxn = 80 + 5;int n,L,cnt;int A[maxn];int dfs(int cur){ if(cnt++ == n){ cnt =...

2018-08-17 00:38:42 121

原创 524:Prime Ring Problem

Prime Ring Problem#include<bits/stdc++.h>using namespace std;const int maxn = 17;int n;int A[maxn],vis[maxn],p[2*maxn];int isPrime(int n){ for(int i = 2;i <= int(sqrt(n));i++){ ...

2018-08-16 00:12:41 113

原创 10976:Fractions Again?!

Fractions Again?!x 要用 long long。#include<bits/stdc++.h>using namespace std;const int maxk = 10000;int k;long long x[2*maxk];int y[2*maxk];int judge(int y){ long long x = k*y/(y-k...

2018-08-14 12:35:18 131

原创 11059:Maximum Product

Maximum Product#include<bits/stdc++.h>using namespace std;const int maxn = 20;int n;int seq[maxn];int main(){ // freopen("data.in","r",stdin); // freopen("data.out","w",stdout);...

2018-08-14 11:49:42 127

原创 725:Division

Division#include<bits/stdc++.h>using namespace std;const int maxn = 64 + 5;int n,a[30240][6];int num,kase = 0,cnt = 0;int Pow(int a,int b){ int n = 1; while(b--) n *= a; retu...

2018-08-14 00:06:43 134

原创 806:Spatial Structures

Spatial Structures#include<bits/stdc++.h>using namespace std;const int maxn = 64 + 5;int n,len;int seq[maxn*maxn];char img[maxn][maxn];struct node{ char c = 0; int cnt = 4; ...

2018-08-11 23:25:48 148

原创 1600:Patrol Robot

Patrol Robot这个题还是DFS，不过每个状态除了记录位置之外，还要记录剩余穿越次数，这样一来就变成了三维DFS。对于值为1的点如果剩余穿越次数大于0且该状态未遍历过的话也可以访问。像这种四个方向的话用常量数组比较方便，没必要搞个二重循环，容易出bug。#include<bits/stdc++.h>using namespace std;const int max...

2018-08-10 00:56:31 133

原创 439:Knight Moves

Knight MovesBFS即可，字符串数组 size 定义成了 2 导致输入一直错误，应该是无法存入'\0' 引起的，待会儿再深究。#include<bits/stdc++.h>using namespace std;const int maxn = 8;typedef pair<int,int> P;int d[maxn][maxn];char a...

2018-08-09 23:10:24 93

原创 712:S-Trees

S-Trees#include<bits/stdc++.h>using namespace std;const int maxn = 7;int n,m,t,cnt = 0;char s[2];int a[maxn];char b[maxn];char leaf[int(pow(2,maxn))];char simu(){ int i = 0,j = t...

2018-08-09 22:11:05 141

原创 536:Tree Recovery

Tree Recovery#include<bits/stdc++.h>using namespace std;const int maxn = 30;struct node{ char c; struct node* l = NULL; struct node* r = NULL;};char p[maxn],m[maxn];node* bu...

2018-08-08 23:52:49 97

原创 12171:Sculpture

Sculpture思路：将三维空间网格化，每个长方体占据的所有单元标记为1。求面积的话，DFS所有的单元，依次检查是上下左右前后六个方向上相邻单元是否为1，若否则是表面，面积加+1。求体积的话，从外面某个单元开始DFS，求出外面值为0的单元的个数，那么总单元个数 - 外部值为0的单元个数 = 雕塑体积。但是由于外部单元个数巨大会导致堆栈溢出，所以需要对坐标进行离散化，另外应选BFS。原来v...

2018-08-07 23:54:36 210

原创 10562:Undraw the Trees

Undraw the Trees这题没啥说的，利用DFS进行先序遍历即可，注意 node 可以不是字母，然后 puts() 默认换行的，太久没用都忘了。。#include<bits/stdc++.h>using namespace std;const int maxn = 200 + 5;int T;char G[maxn][maxn];bool isnode(ch...

2018-08-06 23:37:25 106

原创 10305:Ordering Tasks

Ordering Tasks这题比较简单，就是拓扑排序，而且肯定是有向无环图，直接DFS即可。注意数据读取，只要 n 和 m 有一个不为0即可。。。不考虑是否存在环：#include<bits/stdc++.h>using namespace std;const int maxn = 100 + 10;int m,n,t;int visited[maxn];...

2018-08-05 00:29:29 173

原创 816:Abbott's Revenge

Abbott's Revenge一些细节要特别注意#include<bits/stdc++.h>using namespace std;const int maxn = 10;const char* dirs = "NESW";const char* turns = "FLR";struct Node{ int r,c,dir; Node(int a...

2018-07-31 23:39:16 167

Ancient Messages数一数就能发现，题目表中的6个符号从左到右依次有1，3，5，4，0，2个洞，各不相同。这样，只需要数一数输入的符号有几个“白洞”，就能准确地知道它是哪个符号了。至于具体实现，我的思路是：先确定一个符号，找到该符号的空洞个数然后将该符号“擦除”，继续确定下一个符号。具体而言，每次找到一个黑点，然后DFS，如果其周围点为黑点则递归，若为白点且为封闭块则个数加1，最后再次...

2018-06-02 23:52:41 347

原创 572:Oil Deposits

Oil Deposits#include<bits/stdc++.h>using namespace std;const int maxn = 100 + 5;int m,n,cnt;char graph[maxn][maxn];void dfs(int x,int y){ graph[x][y] = '*'; for(int dx = -1;dx <=...

2018-06-01 12:58:50 121

原创 297:Quadtrees

Quadtrees建树递归，合并也递归。在合并的时候要注意只有两个没有子节点的节点之间才可以合并，可能会遇到三种情况：1. 两个都是最小单元（相对本身），直接合并；2. 其中一个有子节点，依次其将其子节点与另一个节点合并；3. 两个都有子节点，依次将其子节点按顺序进行合并（两者此时子节点面积必定相同，思考一下即可）。其中unit 为最小单元面积，每次划分都变为其本身的1/4，上述过程递归进行即可。...

2018-05-31 23:22:02 142

空空如也

空空如也