2011-11-21 training record personal training (III)

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;
}