AC之路

Leetcode 989. Add to Array-Form of Integer

总计 252 字
题目描述 For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1] Given the array-form A of a non-negative integer X, return the array-form of the integer X+K. // Author: Tecker // date: 2019.2.14 // 132ms, 13.3MB beat 99.19%, 100.00% // time: O(N), space: O(1) or

Leetcode 985. Sum of Even Numbers After Queries

总计 188 字
题目描述 时间复杂度:O(N) 空间复杂度:O(1) // Author: Tecker // 176ms, 28.7MB; beat 96.40%, 100% class Solution { public: vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int> >& queries) { vector<int> res(A.size(), 0); int sum=0; A[queries[0][1]]+=queries[0][0]; for(int &num : A) { if (num%2==0) sum+=num; } res[0]=sum; for(int i=1;i<queries.size();++i) { int val=queries[i][0]; int idx=queries[i][1]; int tmp =

poj 3616 Milking Time

总计 150 字
原题地址 知识点:权值区间DP 解题报告 #include <cstdio>#include <algorithm>#include <iostream>#include <vector> using namespace std; struct P { int start, end, e; }; bool cmp(const P &a, const P &b) { return a.start < b.start; } int N, M, R; struct P a[1002]; int dp[1002]; int main() { scanf("%d %d %d", &N, &M, &R); int i, j; for(i=0;i<M;i++) {

poj 2385 Apple Catching 0ms

总计 258 字
原题地址 知识点:DP 解题报告 #include <cstdio>#include <algorithm>#include <iostream> using namespace std; // j部分定义成 31 时不行? 向前计算的时候有移动 0,..., 30次,共 31 个状态,因此要定义成 32 // d[第

poj 2229 Sumsets

总计 221 字
原题地址 知识点:DP 解题报告 #include <cstdio>#include <string.h> int sum; int d[1000001]; int main() { scanf("%d", &sum); int i; // 初始化唯一确定方案数,d[1] 为 1 表示 1 的分解方案只有 1 种 d[1] = 1; for(i=2;i<=sum;++i) { // 找规律,当 i

poj 3176 Cow Bowling

总计 94 字
原题地址 知识点:DP 解题报告 #include <cstdio>#include <algorithm>#include <iostream> using namespace std; int a[350][350]; int d[350][350]; int N; int main() { scanf("%d", &N); int i, j; for(i=0;i<N;++i) { for(j=0;j<i+1;++j) { scanf("%d", &a[i][j]); } } d[0][0] = a[0][0]; for(i=0;i<N-1;++i) { for(j=0;j<=i;++j) { // 注意这里记忆计算让重叠路径的值最大的技

Poj 3262 Protecting the Flowers

总计 150 字
原题地址 知识点:贪心 解题报告 #include <cstdio>#include <iostream>#include <algorithm>#include <vector> using namespace std; struct P { int t, d; }; // 贪心使得代价最小 // cost = 2 * T * (total - D) // 因此 D越大,T越小越好 // 重点:转换成 D / T

poj 1017 Packets

总计 316 字
知识点:贪心 解题报告 #include <cstdio>#include <algorithm> int square[7]; // 解法:每次都先放最大 int solve() { int res = 0; // 6x6 直接成一块 res += square[6]; // 5x5 先成一块,再补 1x1 res += square[5]; square[1] -= 11 * square[5]; // 4x4 先成一块,然后

poj 3040 Allowance

总计 298 字
知识点: 贪心 解题报告 #include <cstdio>#include <iostream>#include <algorithm>#include <vector>#include <string.h>#include <limits> using namespace std; struct Coin { int d; int b; }; bool cmp(const Coin &a, const Coin &b) { return a.d > b.d; } vector<Coin> v; int N, C; int need_count[20]; int main() { scanf("%d %d", &N, &C); int res = 0; for(int i=0;i<N;i++) { struct Coin c; scanf("%d %d", &c.d, &c.b); if

poj 1979 Red and Black

总计 161 字
知识点:DFS solution #include <cstdio> int W, H; char tile[25][25]; int pos_x, pos_y; int sh_x[4] = {0, 0, -1, 1}; int sh_y[4] = {1, -1, 0, 0}; int res = 0; void solve(int x, int y) { tile[y][x] = '#'; res++; for (int i=0;i<4;i++) { int new_x = x + sh_x[i]; int new_y = y + sh_y[i]; if (new_x >= 0 && new_x <W &&