6.20 --- 6.23
发呆..
6.24
周杰伦的床边故事>.<...............开心
cf349 div2
想到了数的位数不会超过7位，但是暴力的姿势不对
自己 是每一位 去枚举，然后还要枚举分割点，还要判重，很麻烦
还崩掉了
标程的办法，直接枚举数值
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 int main() { 9 int n, m;10 cin >> n >> m;11 12 int len1 = 1, len2 = 1;13 for (int a = 7; a < n; a *= 7)14 len1 += 1;15 for (int b = 7; b < m; b *= 7)16 len2 += 1;17 18 int ans = 0;19 if (len1 + len2 <= 7)20 for (int i = 0; i != n; ++i)21 for (int j = 0; j != m; ++j) {22 int used[8];memset(used,0,sizeof(used));23 24 for (int a = i, k = 0; k != len1; a /= 7, ++k)25 used[a % 7] += 1;26 for (int b = j, k = 0; k != len2; b /= 7, ++k)27 used[b % 7] += 1;28 int flag = 0;29 for(int i = 0;i < 7;i++){30 if(used[i] > 1){31 flag = 1;32 }33 }34 if(!flag) ans++;35 }36 37 cout << ans << "\n";38 39 return 0;40 }
6.25
D题要用到树的重心，还没有写过
poj
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int maxn = 2e4+5; 9 int n,dp[maxn],sz[maxn];10 vector g[maxn];11 12 void dfs(int u,int fa){13 sz[u] = 1;14 for(int i = 0;i < g[u].size();i++){15 int v = g[u][i];16 if(v == fa) continue;17 dfs(v,u);18 sz[u] += sz[v];19 dp[u] = max(dp[u],sz[v]);20 }21 dp[u] = max(dp[u],n-sz[u]);22 }23 24 int main(){25 int T;26 scanf("%d",&T);27 while(T--){28 scanf("%d",&n);29 for(int i = 1;i <= n;i++) g[i].clear();30 memset(sz,0,sizeof(sz));31 memset(dp,0,sizeof(dp));32 int u,v;33 for(int i = 1;i < n;i++){34 scanf("%d %d",&u,&v);35 g[u].push_back(v);36 g[v].push_back(u);37 }38 dfs(1,0);39 /* for(int i = 1;i <= n;i++){40 printf("dp[%d] = %d\n",i,dp[i]);41 printf("sz[%d] = %d\n",i,sz[i]);42 }*/43 int ans1 = 1,ans2 = dp[1];44 for(int i = 2;i <= n;i++){45 if(dp[i] < ans2){46 ans2 = dp[i];47 ans1 = i;48 }49 }50 printf("%d %d\n",ans1,ans2);51 }52 return 0;53 }
看了一晚上D还是没有看懂......TwT/
6.26
看C++primer
第六章
用指针形参交换两个整数的值
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 void swa(int *p1,int *p2){ 8 int tmp; 9 tmp = *p1;10 *p1 = *p2;11 *p2 = tmp;12 }13 14 int main(){15 int a = 2,b = 5;16 int *pa,*pb;17 pa = &a;pb = &b;18 swa(pa,pb);19 printf("a = %d b = %d\n",a,b);20 21 return 0;22 }
又是好多天没刷 leetcode TwT...
leetcode 102
二叉树的层次遍历，但是 因为 题目的类定义的 ans 是 vector<vector<int> > 这种的
所以得把每层 的一个vector 放进去
re 了好久..
1 class Solution{ 2 public: 3 vector > levelOrder(TreeNode* root){ 4 vector >ans; 5 if(root == NULL) return ans; 6 queue q; 7 q.push(root); 8 while(!q.empty()){ 9 vector tmp;10 int sz = q.size();11 for(int i = 0;i < sz;i++){12 TreeNode* p = q.front();q.pop();13 tmp.push_back(p->val);14 if(p->left) q.push(p->left);15 if(p->right) q.push(p->right);16 }17 ans.push_back(tmp);18 }19 // reverse(ans.begin(),ans.end());20 return ans;21 }22 };
leetcode 107
和上一题一样，reverse一下 ans
1 class Solution{ 2 public: 3 vector > levelOrderBottom(TreeNode* root){ 4 vector >ans; 5 if(root == NULL) return ans; 6 queue q; 7 q.push(root); 8 while(!q.empty()){ 9 vector tmp;10 int sz = q.size();11 for(int i = 0;i < sz;i++){12 TreeNode* p = q.front();q.pop();13 tmp.push_back(p->val);14 if(p->left) q.push(p->left);15 if(p->right) q.push(p->right);16 }17 ans.push_back(tmp);18 }19 reverse(ans.begin(),ans.end());20 return ans;21 }22 };
leetcode 103
隔层翻转一下
1 class Solution{ 2 public: 3 vector > zigzagLevelOrder(TreeNode* root){ 4 vector >ans; 5 if(root == NULL) return ans; 6 queue q; 7 q.push(root); 8 int flag = 0; 9 while(!q.empty()){10 vector tmp;11 int sz = q.size();12 for(int i = 0;i < sz;i++){13 TreeNode* p = q.front();q.pop();14 tmp.push_back(p->val);15 if(p->left) q.push(p->left);16 if(p->right) q.push(p->right);17 }18 if(flag) reverse(tmp.begin(),tmp.end());19 ans.push_back(tmp);20 flag = !flag;21 }22 return ans;23 }24 };
good_bye 2015 d
看题解< T 3T >
dp[i][j] 表示 以 i 为结尾的，最后一段的长度为 j 的方案数
dp[i][j] = sum(dp[i-j][min(j-1,i-j)]) + (dp[i-j][j] ，如果(i-j+1,i) 大于 (i-2*j+1,i-j))的话
所以需要 预处理 一个 lcp[i][j]，表示 以 i 开头，j 开头 的最长公共前缀是多长
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int mod = 1e9+7; 8 const int maxn = 5e3+5; 9 int dp[maxn][maxn],g[maxn][maxn],lcp[maxn][maxn];10 int n;11 char s[maxn];12 13 int dayu(int i,int j,int len){14 if(lcp[i][j] >= len) return 0;15 int cc = lcp[i][j];16 return s[i+cc] > s[j+cc];17 }18 19 void solve(){20 memset(lcp,0,sizeof(lcp));21 for(int i = n;i >= 1;i--){22 for(int j = n;j >= 1;j--){23 if(s[i] == s[j]) lcp[i][j] = lcp[i+1][j+1]+1;24 }25 }26 27 memset(dp,0,sizeof(dp));memset(g,0,sizeof(g));28 for(int i = 1;i <= n;i++){29 for(int j = 1;j < i;j++){30 g[i][j] = g[i][j-1];31 if(s[i-j+1] == '0') continue;32 dp[i][j] = (dp[i][j] + g[i-j][min(j-1,i-j)])%mod;33 if(dp[i-j][j] && dayu(i-j+1,i-2*j+1,j)){34 dp[i][j] = (dp[i][j]+dp[i-j][j])%mod;35 }36 g[i][j] = (g[i][j]+dp[i][j])%mod;37 }38 dp[i][i] = 1;39 g[i][i] = (g[i][i-1]+dp[i][i])%mod;40 }41 int ans = 0;42 for(int i = 1;i <= n;i++){43 ans = (ans+dp[n][i])%mod;44 }45 printf("%d\n",ans);46 }47 48 int main(){49 while(scanf("%d",&n) != EOF){50 scanf("%s",s+1);51 solve();52 }53 return 0;54 }