首页 > 代码库 > UESTC 2014 Summer Training #7 Div.2
UESTC 2014 Summer Training #7 Div.2
DAY7一开始状态还行,最高纪录rank7,然后没力气了,一直跌到rank24,问题还是很多呐。昨天总结的问题依然很大。
Problem A UVA 12377
就一开始还是慌了,没审清楚题意就去WA了一发。
大意是给你一个数字表示的字符串，最高20位，第一表示有N个质数，后面是其幂的非降序排列，所求能表示的数个数。
简单的排列组合题，不过需要处理出2~END的不同划分，并且满足非降序，用dfs处理即可。
具体就是dfs过程中记录下每一个数字出现的次数，因为相同的次数是不计顺序的，需要在统计时除以cnt!(阶乘)
对于每一种划分，增加的方案数 = 9!/(9-N+1)!/cnt[i]!
我的做法是dfs字符串s,上一个数x, 当前划分出的个数n,每次按照剩余的长度枚举当前划分出的数字,并且满足不小于上一个数x,满足的话,
还需要纪录下其出现的次数,最后dfs的串为空的时候检查划分出的个数,满足开始统计
下午在做的时候,也出现了很多小问题:
1.划分串长达19位,如果个数为1,2之类,转化为整数就可能会爆炸,需要用long long,一组数据 211...(19个1)
2.fgets整行读入,字符串末尾带上了\n,需要自己处理掉,不然strlen返回值不是理想结果
3.!!!!!!!!!!!!!!!!中间可能会出现0,而0不能作为一个数的前导,包括0,所以如果dfs枚举出字符串的前导为0时,中断(<---下午没A的原因
这道题自己的问题还是很大的,一开始的审题不仔细,对数据考察的不深入,爆int,以及最后默认没有0,都是很难解决的"小毛病",却是很致命的.
#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>using namespace std;const int maxn = 25;const int A[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};int T, tot;long long numcnt[maxn], hashnum[maxn];long long ans;char code[maxn];void dfs(char *s, long long x, int num, int upper){ if(*s == 0 && upper == num) { long long cnt = 1; for(int i = 0; i < upper; i++) cnt *= (9-i); for(int i = 0; i < tot; i++) cnt /= A[numcnt[i]];// cout << tot << endl;// cout << "cnt" << cnt << endl; ans += cnt; } int len = (int)strlen(s);// cout << x << ‘ ‘ << len << endl; for(int i = 1; i <= len; i++) { long long _last; char tmp[maxn]; strncpy(tmp, s, sizeof(char)*i); tmp[i] = 0; sscanf(tmp, "%lld", &_last); if(_last < x || tmp[0] == ‘0‘) continue; int pos; bool has = false; for(int j = 0; j < tot; j++) if(hashnum[j] == _last) { has = true; numcnt[j]++; pos = j; break; } if(!has) { hashnum[tot] = _last; pos = tot++; numcnt[pos] = 1; } dfs(s+i, _last, num+1, upper); numcnt[pos]--; if(!has) tot--; }}int main(){#ifdef LOCAL freopen("A.in", "r", stdin);#endif scanf("%d", &T); getchar(); while(T--) { fgets(code, maxn, stdin); int len = strlen(code); while(code[len-1] < ‘0‘ || code[len-1] > ‘9‘) { code[len-1] = 0; len--; } tot = 0; ans = 0; memset(hashnum, 0, sizeof(hashnum)); memset(numcnt, 0, sizeof(numcnt)); dfs(code+1, 0, 0, code[0]-‘0‘);// cout << cnt << endl; printf("%lld\n", ans); } return 0;}
Problem F UVA 12382
对于一个M*N的01矩阵,给出每行每列要求出现1的最少个数,球要满足条件填入1的最少个数。
贪心的原理还是不是很理解,以下废话只是个人的一些思考
(废话->)由于交叉点的1可以同时满足行列,就看怎么让交叉点最多,比如以填行同时使交叉点最多,可以对行需求排序,从高到低放置1,放置第i行的时候,为了使得
下一行,能够放置的列数更多(交叉情况)(避免列不够而这行没有满足需要添加不交叉点),如果列放置需求(列数)已经小于这行需求,就在这行其他位置再填入一些1
最后可能有些列没满足,加上即可
由于需要取出需求最大的列,用优先队列维护,注意是k列都取出后,再减一放进去,而不是边pop边push,小于等于0的列就不用push了
/**Updated**/
用模拟的方法去实现,我们肯定要将每行都至少放置需要的个数满足,即每行放置需求个数的1,现在考虑这些1放在哪些位置,贪心的策略是,选择需求最多的列来放置,这样可以保证在做下一行的时候,能够选择的列更多(举个列子,列需求1 2,行需求1 2 ...,如果第一行放置1 0,第二行就只能放置为0 1,再去放上1个不交叉的,这种策略就不是最优的:保证尽量多的交叉点)
/**Updated**/
#include <iostream>#include <cstdio>#include <cstdlib>#include <queue>#include <vector>using namespace std;const int maxn = 1000+50;int T, m, n, ans;priority_queue<int, vector<int>, less<int> > q;int main(){#ifdef LOCAL freopen("I.in", "r", stdin);#endif scanf("%d", &T); while(T--) { scanf("%d%d", &m, &n); for(int i = 0; i < m; i++) { int tmp; scanf("%d", &tmp); q.push(tmp); }// cout << "top " << q.top() << endl; ans = 0; for(int i = 0; i < n; i++) { int col; scanf("%d", &col); int tot = 0; int tofill[maxn]; for(int j = 0; j < col; j++) if(!q.empty()) { tofill[tot++] = q.top(); q.pop(); } for(int j = 0; j < tot; j++) if(tofill[j] > 1) q.push(tofill[j]-1); ans += col;// if(T == 1) cout << ans << endl; } while(!q.empty()) {// if(T == 2) cout << "top " << q.top() << endl; ans += q.top(); q.pop(); } printf("%d\n", ans); } return 0;}
Problem H UVA 12384
先预处理出素数,然后扫一遍,每个数都往前查找,寻找第一个大于x的数的位置,由于s[i]表示以a[i]为尾的连续非降序列个数,所以如果x>=a[i],指针可以直接跳s[i]个单元,
当然这种方法算比较渣的。。吗?
还有一种思路是:单调队列。。。我没听懂。。。
再一种思路:线段树！
我们可以把a[i]作为点的坐标,i作为该点的值p[a[i]] = i,计算s[i]的时候,需要往前寻找第一个a[j]>a[i],即!查找a[j]<a[i]的最大的j!,可以转化为线段树查找最大值
线段1~a[i]-1的最大值就是要找的j...
理解了好久T T
#include <iostream>#include <cstdlib>#include <cstdio>#include <cmath>#include <cstring>using namespace std;const int maxn = 100000+50;int T, n, m, tot;int prime[maxn*10*5], x[maxn], s[maxn];long long sum;bool isprime(int x){ if(x == 2) return true; if(x % 2 == 0) return false; for(int i = 3, t = sqrt(x); i <= t; i += 2) if(x % i == 0) return false; return true;}int main(){#ifdef LOCAL freopen("H.in", "r", stdin);#endif scanf("%d", &T); for(int i = 2, t = maxn*2*10; i < t; i++) if(isprime(i)) prime[++tot] = i;// cout << tot << endl; while(T--) { scanf("%d%d", &n, &m); sum = 0; memset(s, 0, sizeof(s)); for(int i = 1; i <= n; i++) { if(i == 1) s[i] = 1; else if(prime[i] %m >= prime[i-1] %m) { int j = i-s[i-1]; s[i] = s[i-1]; while(j >= 1 && prime[i] % m >= prime[j] % m) { s[i] += s[j]; j -= s[j]; }/* s[i] = s[i-1]; int j = i-s[i-1]-1, cnt = 1; while(j >= 1 && prime[i] % m >= prime[j] % m) { cnt++; j--; } s[i] += cnt; */ } else s[i] = 1; sum += s[i]; //cout << s[i]; } //cout << sum << endl; printf("%lld\n", sum % m); } return 0;}
顺带练习一发筛法,后面那个break不懂哟
void getPrime(){ int maxm = maxn*40; for(int i = 2; i <= maxm; i++) { if(!flag[i]) prime[++tot] = i; for(int j = 1; j <= tot && i*prime[j] <= maxm; j++) { flag[i*prime[j]] = true; if(i % prime[j] == 0) break; } }}
Problem I UVA 12385
正规做法 DP
容易注意到需要考虑每一个字符上一次出现的位置,记为last[c[i]],显然a-a-a比a---a更优
f[c]表示以c为尾巴的最长序列 f[c] = max(f[c-1], f[last[c]]+1), last[c]不存在的话,f[c] = 0,看了半天题解才懂。。懒得写了。。。
傻叉瞎搞法:
扫一遍把所有的线段跑出来,当然不包括a-a-a这种,就a-a的,然后sort下贪心。。。
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>using namespace std;const int maxn = 100000+50;struct interval{ int x1, x2; void set(int x1, int x2) { this->x1 = x1; this->x2 = x2; }}seg[maxn];int T, n, tot;int lastn[maxn];int cmp(const interval &a, const interval &b){ if(a.x2 == b.x2) return a.x1 > b.x1; else return a.x2 > b.x2;}int main(){#ifdef LOCAL freopen("I.in", "r", stdin);#endif scanf("%d", &T); while(T--) { memset(lastn, -1, sizeof(lastn)); tot = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); if(lastn[x] != -1) {// cout << x << ‘ ‘ << lastn[x] << ‘ ‘ << i << endl; seg[tot].set(lastn[x], i); tot++; } lastn[x] = i; } sort(seg, seg+tot, cmp); int left = maxn*2; long long ans = 0; for(int i = 0; i < tot; i++) { if(seg[i].x2 <= left) { ans++; left = seg[i].x1; } else if(seg[i]. x1 > left) left = seg[i].x1; } printf("%lld\n", ans); } return 0;}