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-8typedef 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');elseprintf("%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-8typedef 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-8typedef 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");elseputs("NO");}Delete( rt );}return 0;}
理想的路总是为有信心的人预备着
