当前位置:网站首页>2011-11-21 training record personal training (III)
2011-11-21 training record personal training (III)
2022-07-05 08:52:00 【Qizi K】
A - DNA Consensus String UVA - 1368
String emulation qwq.
#include<bits/stdc++.h>
using namespace std;
const int N = 1010,M = 105;
int t,n,m;
string book[N];
int main(){
cin >> t;
while(t --){
int ans = 0;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; ++i)
cin >> book[i];
for(int i = 0; i < m; ++i){
int a = 0, c = 0, g = 0, t = 0;
for(int j = 1; j <= n; ++j){
if(book[j][i] == 'A') a ++;
else if(book[j][i] == 'C') c ++;
else if(book[j][i] == 'G') g ++;
else t ++;
}
if(a >= c && a >= g && a >= t) putchar('A'), ans += (c + g + t);
else if(c >= g && c >= t) putchar('C'), ans += (a + g + t);
else if(g >= t) putchar('G'), ans += (c + a + t);
else putchar('T'), ans += (c + g + a);
//printf("a = %d c = %d g = %d t = %d ans = %d\n", a,c,g,t,ans);
}
printf("\n%d\n", ans);
}
return 0;
}
B - Funny Car Racing UVA - 12661
tips: Shortest path deformation . Yes n Strip road m A road junction , Each intersection is opened according to a fixed cycle 、 close , There is a certain time to pass the level . Ask the shortest time from the beginning to the end .
Convert to the shortest path , The time passed is converted into distance , Then look at the current intersection , Is the intersection open or closed ( modulus ), Then consider the time of passing , obtain sum. use dis[u]+sum To update dis[j], It is the shortest routine operation .
Pit point : It is possible that the time of passing through the intersection is longer than that of opening the intersection , Then this intersection cannot be passed !
It's still a good short-circuit deformation QWQ
#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N = 100010;
int h[N], ne[N], open[N], close[N], pass[N], e[N], idx;
int dis[N],n,m,s,t;
bool st[N];
struct HeapNode{
int u, d;
bool operator < (const HeapNode& rhs) const{
return d > rhs.d;
}
};
void add(int a, int b, int c, int d, int ee){
e[idx] = b, open[idx] = c, close[idx] = d, pass[idx] = ee,ne[idx] = h[a], h[a] = idx ++;}
int Dijkstra(int s){
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
priority_queue<HeapNode> q;
q.push(HeapNode{
s, 0});
while(!q.empty()){
HeapNode fr = q.top(); q.pop();
int u = fr.u;
if(st[u]) continue;
st[u] = true;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
int tmp = dis[u] % (open[i] + close[i]), sum = 0;
if(pass[i] <= open[i]){
if(tmp >= 0 && tmp < open[i]){
// It's on now
if(tmp + pass[i] <= open[i]) sum = pass[i];
else sum = pass[i] + open[i] - tmp + close[i];
}else sum = pass[i] + close[i] + open[i] - tmp;
if(dis[j] > dis[u] + sum){
dis[j] = dis[u] + sum;
q.push(HeapNode{
j, dis[j]});
}
}
}
}
return dis[t];
}
int main(){
int cases = 0;
while(cin >> n >> m >> s >> t){
memset(h, -1, sizeof h);
idx = 0;
memset(st, 0, sizeof st);
for(int i = 1; i <= m; ++i){
int aa,bb,cc,dd,ee;
cin >> aa >> bb >> cc >> dd >> ee;
add(aa,bb,cc,dd,ee);
}
printf("Case %d: %d\n", ++cases, Dijkstra(s));
}
return 0;
}
C - Unique Snowflakes UVA - 11572
tips: Find the length of the longest continuous interval , There are no two identical numbers in this interval . Ruler method .
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int t,n,book[N];
int main(){
cin >> t;
while(t --){
scanf("%d",&n);
for(int i = 1; i <= n; ++i) scanf("%d",&book[i]);
int l = 1, r = 1, ans = 0;
map<int, int> mp;
while(true){
//printf("l = %d r = %d\n", l, r);
while(r <= n && !mp[book[r]]) mp[book[r++]] ++;
ans = max(ans, r - l);
if(r > n) break;
mp[book[l++]]--;
}
printf("%d\n", ans);
}
return 0;
}
D - Updating a Dictionary UVA - 12504
tips: Each group gives two dictionaries , Ask about the changes before and after the dictionary ( Insert ? modify ? Delete ?).
Very disgusting string emulation , Investigate vector,map,string The operation of .
It can be used stringstream Simplify simplify (j Comments in the code ).
Pay attention to the pits : It may be an empty dictionary ; Maybe it's just key No, value, This situation should be abandoned .
This kind of problem should be written regularly qwq It is a great test of code ability and details .
#include<bits/stdc++.h>
#include<map>
#include<vector>
using namespace std;
int t;
char c;
map<string, string> mp1, mp2;
map<string, string> :: iterator it1, it2;
string str;
void make(int flag){
string s1 = "", s2 = "";
for(int i = 1; str[i]; ++i){
c = str[i];
if(c >= 'a' && c <= 'z') s1 += c;
else if(c == ':') continue;
else if(c >= '0' && c <= '9') s2 += c;
else if(c == ',' || c == '}'){
//cout << "s1 " << s1 << " s2 " << s2 << endl;
if(s1 != "" && s2 != ""){
if(flag == 1) mp1[s1] = s2;
else mp2[s1] = s2;
s1 = s2 = "";
}
}
}
}
/* void make(int flag) { // Partition to get a dictionary for (auto& ch : str) // take {},: Replace with space if (ch == '{' || ch == '}' || ch == ',' || ch == ':') ch = ' '; stringstream input(str); string sk, sv; while (input >> sk >>sv ){ if(flag == 1) mp1[sk] = sv; // stringstream Split by space else mp2[sk] = sv; } } */
void judge(){
vector<string> insert,remove,update;
vector<string> :: iterator niko;
bool flag = false;
for(it1 = mp1.begin(), it2 = mp2.begin(); it1 != mp1.end() && it2 != mp2.end(); ){
//cout << "1 " << it1->first << " 2 " << it2->first << endl;
if(it1->first == it2->first){
if(it1->second != it2->second)
update.push_back(it1->first), flag = true;
it1 ++, it2 ++;
}else if(!mp2.count(it1->first)){
flag = true;
remove.push_back(it1->first);
it1 ++;
}else if(!mp1.count(it2->first)){
flag = true;
insert.push_back(it2->first);
it2 ++;
}
}
while(it1 != mp1.end()) remove.push_back(it1->first), it1 ++, flag = true;
while(it2 != mp2.end()) insert.push_back(it2->first), it2 ++, flag = true;
if(insert.size()){
printf("+");
niko = insert.begin();
cout << *niko;
for(niko = insert.begin() + 1; niko != insert.end(); ++niko)
cout << "," << *niko;
cout << endl;
}
if(remove.size()){
printf("-");
niko = remove.begin();
cout << *niko;
for(niko = remove.begin() + 1; niko != remove.end(); ++niko)
cout << "," << *niko;
cout << endl;
}
if(update.size()){
printf("*");
niko = update.begin();
cout << *niko;
for(niko = update.begin() + 1; niko != update.end(); ++niko)
cout << "," << *niko;
cout << endl;
}
if(!flag) puts("No changes");
}
int main(){
cin >> t;
while(t --){
mp1.clear(), mp2.clear();
cin >> str;
make(1);
cin >> str;
make(2);
judge();
cout << endl;
}
return 0;
}
H - The Counting Problem UVA - 1640
tips: digit DP, Count the number of times each number appears .
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 25;
int num[N];
ll dp[N][N],l,r;
ll dfs(int pos, bool limit, bool lead,ll sum, int digit){
if(pos == -1) return sum;
if(!limit && !lead && dp[pos][sum] != -1) return dp[pos][sum];
int up = limit ? num[pos] : 9;
ll ans = 0;
for(int i = 0; i <= up; ++i)
ans += dfs(pos - 1, (limit && i == up), (lead && i == 0), sum + (i == digit && (i || !lead)), digit);
if(!limit && !lead) dp[pos][sum] = ans;
return ans;
}
ll solve(int x, int digit){
memset(dp, -1, sizeof dp);
int pos = 0;
while(x){
num[pos ++] = x % 10;
x /= 10;
}
return dfs(pos - 1, true, true, 0, digit);
}
int main(){
while(~scanf("%lld%lld",&l,&r) && (l && r)){
if(l > r) swap(l, r);
for(int i = 0; i <= 9; ++i)
printf("%lld%c", solve(r,i) - solve(l - 1, i), (i == 9 ? '\n' : ' '));
}
return 0;
}
边栏推荐
- 某公司文件服务器迁移方案
- js异步错误处理
- C#绘制带控制点的Bezier曲线,用于点阵图像及矢量图形
- Confusing basic concepts member variables local variables global variables
- Task failed task_ 1641530057069_ 0002_ m_ 000000
- Redis实现高性能的全文搜索引擎---RediSearch
- Halcon clolor_ pieces. Hedv: classifier_ Color recognition
- ABC#237 C
- Guess riddles (9)
- Programming implementation of subscriber node of ROS learning 3 subscriber
猜你喜欢
随机推荐
Guess riddles (3)
Array,Date,String 对象方法
GEO数据库中搜索数据
特征工程
[daiy4] copy of JZ35 complex linked list
Yolov4 target detection backbone
Mengxin summary of LIS (longest ascending subsequence) topics
Chris LATTNER, the father of llvm: why should we rebuild AI infrastructure software
Ros- learn basic knowledge of 0 ROS - nodes, running ROS nodes, topics, services, etc
Multiple linear regression (sklearn method)
LLVM之父Chris Lattner:为什么我们要重建AI基础设施软件
Halcon blob analysis (ball.hdev)
Shift operation of complement
Solutions of ordinary differential equations (2) examples
asp.net(c#)的货币格式化
Solution to the problem of the 10th Programming Competition (synchronized competition) of Harbin University of technology "Colin Minglun Cup"
Guess riddles (10)
Kubedm series-00-overview
猜谜语啦(8)
Count of C # LINQ source code analysis