A Artwork

输入：

n，m表示原图为n*m个白色方格，输入x1,y1,x2,y2表示将x1,y1,x2,y2涂为黑色。

输出：

对于每个x1,y1,x2,y2输入当前图案白色联通块的数目。

思路：

先维护得到最后图案的形状，包括每个黑色方块的厚度。

对于每个x1,y1,x2,y2倒序访问，将其对应位置的黑色还原为白色。通过上下左右的联通关系，更新并查集得到每组的答案。

#include
      
       using namespace std;struct sc{    int a,b,c,d;} edg[10010];int p[1100100],g[1010][1010],ans[10010];int dx[]= {
    0,1,-1,0};int dy[]= {
    1,0,0,-1};int n,m,q,cnt=0,k=0;int f(int x){    return x==p[x]?x:p[x]=f(p[x]);}void u(int a,int b){    int x=f(a),y=f(b);    p[x]=y;}int id(int x,int y){    return x*(m+2)+y+1;}int main(){    scanf("%d %d %d",&n,&m,&q);    memset(g,0,sizeof g);    for(int i=0; i<=n+1; i++)        for(int j=0; j<=m+1; j++)        {            p[id(i,j)]=id(i,j);            if(!i||!j|i>n||j>m)g[i][j]=1;        }    for(int i=0; i
       
        =0; i--)printf("%d\n",ans[i]);}
       
      

反思:

场上心里闪过并查集的念头，但是只想到了对于黑色进行并查集，没有从一个角度看问题，比如反过来看，看答案的对应面，比如补集，或者倒着获得答案。

数组开小了， 应该算清楚每个数组的范围。

B Bless You Autocorrect!

输入:

n,m表示下面有n,m个串，n表示手机里的字典词按照出现的顺序表示优先级，m表示你想输入的单词。

输出:

对于每个你想输入的单词，输出最小打出它需要的按键次数。

思路:

用字典树来存储单词，字典树（树上的每一个串的子串都会有一个id），通过这些id和每个串每打一个按键可以得到的另外一个串建立双向边。

跑一遍bfs即可获得每个串可以打出需要的最小按键数量。

#include
      
       using namespace std;const int maxn=1e6;char s[maxn];int tot=0,tree[30][maxn],edg=0,head[maxn],dp[maxn],cnt[maxn],vis[maxn];struct sc{    int to,nxt;}p[6*maxn];void add(int a,int b){    p[edg]={b,head[a]},head[a]=edg++;}void inser(){    int l=strlen(s),nxt=0;    for(int i=0;i
       

q; for(q.push(0);!q.empty();q.pop()) { int v=q.front(); for(int i=head[v];~i;i=p[i].nxt) { int u=p[i].to; if(!vis[u]) { vis[u]++; dp[u]=dp[v]+1; q.push(u); } } }}int ans(){ int l=strlen(s),mi=l,nxt=0,u; for(int i=0;i