A - Chewbaсca and Number
: 求“倒置”后的最小的数,倒置为每个位上的数x = min(x, 9-x)。注意无前导0
#include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 #define pi acos(-1.0) #define eps 1e-8 typedef long long ll; const int inf = 0x3f3f3f3f; char a[22]; int main() { while(~scanf("%s", a)) { int i = 0; if( a[i] == '9' ) printf("%c", a[i]) ,i++; for(; a[i]; i++ ) if( a[i] >= '5' ) printf("%d", 9 - a[i] + '0'); else printf("%c", a[i]); puts(""); } return 0; }
B - Han Solo and Lazer Gun
二维坐标系里面,求用最少的激光射完所有的点,在同一直线上都可以一发搞定。hash下即可
#include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 #define pi acos(-1.0) #define eps 1e-8 typedef long long ll; const int inf = 0x3f3f3f3f; struct node{ int x, y; }p; set <int> s; set <int> :: iterator it; int main() { int a, b, n; while( ~scanf("%d%d%d", &n, &a, &b)) { s.clear(); bool OK[2] = {0, 0}; while( n-- ) { scanf("%d%d", &p.x, &p.y ); p.x -= a, p.y -= b; if( p.x == 0 ) { if( !OK[0] ) OK[0] = 1, s.insert( 0 ); continue; } if( p.y == 0 ) { if( !OK[1] ) OK[1] = 1, s.insert( 1 ); continue; } int c = __gcd(p.x, p.y); p.x /= c, p.y /= c; if( p.x < 0 ) p.x *= -1, p.y *= -1; if( s.find( p.x * 10005 + p.y ) == s.end() ) s.insert( p.x * 10005 + p.y ); } cout << s.size() << endl; } return 0; }
C - Watto and Mechanism
先给出n 个字符串,再依次给出m个字符串,求在前n个字符串中是否存在最多只有一个字符不同的串,有YES,无NO
建一个字典树然后dfs。注意剪枝不然会T
#include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 #define pi acos(-1.0) #define eps 1e-8 typedef long long ll; const int inf = 0x3f3f3f3f; const int N = 600100; struct node{ node *nxt[3]; int cnt; node (){ cnt = 0; nxt[0] = nxt[1] = nxt[2] = NULL; } }*rt; char c[N]; bool vis[N]; int n, m; int len; void build_trie( char str[] ) { len = strlen( str ); node *p = rt; for ( int i = 0; i < len; ++i ) { if ( p->nxt[ str[i] - 'a' ] == NULL ) p->nxt[ str[i] - 'a' ] = new node(); p = p->nxt[ str[i] - 'a' ]; } p->cnt = 1; } bool dfs( node *p, int cur, int diff ) { if( cur == len ) { return diff && p->cnt; } int OK = 0; for( int i = 0; i <= 2; ++i ) { if( p->nxt[i] != NULL ) { if ( i == c[cur] - 'a' ) OK |= dfs( p->nxt[i], cur+1, diff ); else { if( diff ) continue; OK |= dfs( p->nxt[i], cur+1, diff+1 ); } } } return OK; } void Delete (node *p) { for (int i = 0; i < 3; ++i) { if (p -> nxt[i] != NULL) { Delete (p -> nxt[i]); } } delete p; } int main() { while( ~scanf("%d%d", &n, &m)) { memset( vis, 0, sizeof( vis ) ); rt = new node(); while( n-- ) { scanf("%s", c); len = strlen( c ); vis[len] = 1; build_trie( c ); } while( m-- ) { scanf("%s", c); len = strlen( c ); if( !vis[ len ] ) { printf("NO\n"); continue; } if( dfs(rt, 0, 0) ) puts("YES"); else puts("NO"); } Delete( rt ); } return 0; }